COMMENT ⊗   VALID 00024 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00004 00002	\input acphdr % Answer pages (double-check position of figures)
C00005 00003	% moved over from V2ANS2 because of page break:
C00008 00004	%folio 790 galley 10 (C) Addison-Wesley 1978	*
C00024 00005	%folio 794 galley 11a (C) Addison-Wesley 1978	*
C00064 00006	%folio 795 galley 11b (C) Addison-Wesley 1978	*
C00068 00007	%folio 796 galley 11c (C) Addison-Wesley 1978	*
C00075 00008	%folio 797 galley 12 (C) Addison-Wesley 1978	*
C00085 00009	%folio 800 galley 13 (C) Addison-Wesley 1978	*
C00093 00010	%folio 802 galley 1a (C) Addison-Wesley 1978	*
C00108 00011	%folio 804 galley 1b (C) Addison-Wesley 1978	*
C00113 00012	%folio 805 galley 2 (C) Addison-Wesley 1978	*
C00131 00013	%folio 810 galley 3 (C) Addison-Wesley 1978	*
C00150 00014	%folio 818 galley 4a (C) Addison-Wesley 1978	*
C00178 00015	%folio 819 galley 4b (C) Addison-Wesley 1978	*
C00189 00016	%folio 821 galley 5 (C) Addison-Wesley 1978	*
C00204 00017	%folio 824 galley 6a (C) Addison-Wesley 1978	*
C00222 00018	%folio 826 galley 6b (C) Addison-Wesley 1978	*
C00229 00019	%folio 828 galley 7 (C) Addison-Wesley 1978	*
C00245 00020	%folio 832 galley 8 (C) Addison-Wesley 1978	*
C00262 00021	%folio 835 galley 9a (C) Addison-Wesley 1978	*
C00327 00022	%folio 840 galley 9b (C) Addison-Wesley 1978	*
C00332 00023	%folio 842 galley 10a (C) Addison-Wesley 1978	*
C00344 00024	\vfill\end
C00345 ENDMK
C⊗;
\input acphdr % Answer pages (double-check position of figures)
\open0=v2ans3.inx
\chpar19←1 % this will prepare a ".JST" file containing justification statistics
\runninglefthead{ANSWERS TO EXERCISES}
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{ANSWER PAGES for THE ART OF COMPUTER PROGRAMMING}
\ctrline{(Volume 2)}
\ctrline{(third half of the answers)}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\ninepoint
\runningrighthead{ANSWERS TO EXERCISES}
\section{4.5.3}
\eject
\setcount0 608
% moved over from V2ANS2 because of page break:
\ansno 42. Suppose that $\|qX\|=|qX-p|$. We can always
find integers $u$ and $v$ such that
$q=uq↓{n-1}+vq↓n$ and $p=up↓{n-1}+vp↓n$, where $p↓n=Q↓{n-1}(A↓2,\ldotss,A↓n)$,
since $q↓np↓{n-1}-q↓{n-1}p↓n=\pm1$. We must have $uv<0$, hence $u(q↓{n-1}X-p↓{n-1})$
has the same sign as $v(q↓nX-p↓n)$, and $|qX-p|=|u|\,|q↓{n-1}X-p↓{n-1}|+
|v|\,|q↓nX-p↓n|$. This completes the proof, since $u≠0$. See Theorem↔6.4S for
a generalization.

\ansno 43. If $x$ is representable, so is the father of $x$ in the \α{Stern--Peirce
tree} of exercise 40; thus the representable numbers form a subtree of that binary
tree. Let $(u/u↑\prime)$ and $(v/v↑\prime)$ be adjacent representable numbers. Then
one is an ancestor of the other; say $(u/u↑\prime)$ is an ancestor of $(v/v↑\prime)$,
since the other case is similar. Then $(u/u↑\prime)$ is the nearest left
ancestor of $(v/v↑\prime)$, so all numbers between $u/u↑\prime$ and $v/v↑\prime$
are left descendants of $(v/v↑\prime)$ and the mediant
$\biglp(u+v)/(u↑\prime+v↑\prime)\bigrp$ is its left son. According to the
relation between regular continued fractions and the binary tree, the mediant
and all of its left descendants will have $(u/u↑\prime)$ as their last
representable $p↓i/q↓i$, while all of the mediant's right descendants will
have $(v/v↑\prime)$ as one of the $p↓i/q↓i$.\xskip(The numbers $p↓i/q↓i$ label
the {\sl fathers} of the `turning-point' nodes on the path to↔$x$.)

\ansno 44. A counterexample for $M=N=100$ is $(u/u↑\prime)={1\over3}$, $(v/v↑\prime)=
{67\over99}$. However, the identity is almost always true, because of (12);
it fails only when $u/u↑\prime+v/v↑\prime$ is very nearly equal to a fraction
that is simpler than $(u/u↑\prime)$.

\ansno 45. See M. S. \α{Waterman}, {\sl BIT \bf17} (1977), 465--478.
%folio 790 galley 10 (C) Addison-Wesley 1978	*
\ansbegin{4.5.4}

\ansno 1. If $d↓k$ isn't prime, its
prime factors are cast out before $d↓k$ is tried.

\ansno 2. No; the algorithm would fail if $p↓{t-1} = p↓t$, giving
``1'' as a spurious prime factor.

\ansno 3. Let $P$ be the product of the first 168 primes.\xskip [{\sl
Note:} Although $P=19590\ldotsm5910$ is a 416-digit number, such a gcd can
be computed in much less time than it would take to do 
168 divisions, if we just want to test whether or not $n$ is prime.]

\ansno 4. In the notation of exercise 3.1--11,$$\sum↓{\mu,\,λ}2↑{\lceil\lg
\max(\mu+1,λ)\rceil}P(\mu,λ)={1\over m}\sum↓{l≥1}f(l)\prod↓{1≤k<l}
\bigglp1-{k\over m}\biggrp,$$
where $f(l)=\sum↓{1≤λ≤l}2↑{\lceil\lg\max(l-λ,λ)\rceil}$.
If $l=2↑{k+\theta}$, where $0<\theta≤1$, we have $f(l)=l↑2(3\cdot2↑{-\theta}-2\cdot
2↑{-2\theta})$, where the function $3\cdot2↑{-\theta}-2\cdot2↑{-2\theta}$
reaches a maximum of $9\over8$ at $\theta=\lg(4/3)$ and has a minimum of 1 at
$\theta=0$ and 1. Therefore the average value of $2↑{\lceil\lg\max(\mu+1,λ)\rceil}$
lies between 1.0 and 1.125 times the average value of $\mu+λ$, and the result
follows.

[Algorithm↔B is a refinement of \α{Pollard}'s original algorithm, which was based
on exercise 3.1--6(b) instead of the (yet undiscovered) result in exercise 3.1--7.
He showed that the least $n$ such that $X↓{2n}=X↓n$ has average value $~(π↑2/12)
Q(m)$; this constant $π↑2/12$ is explained by Eq.\ 4.5.3--21. Hence the average
value of $3n$ in his original method is $~(π/2)↑{5/2}\sqrt m=3.092\sqrt m$.\xskip
Richard \α{Brent} has observed that, as $m→∞$, the density $\prod↓{1≤k<l}\biglp1-k/m
\bigrp=\exp\biglp-l(l-1)/2m+O(l↑3/m↑2)\bigrp$ approaches a normal distribution,
and we may assume that $\theta$ is uniformly distributed. Then ${3{\cdot}2↑{-\theta}
-2{\cdot}2↑{-2\theta}}$ takes the average value $3/(4\ln2)$, and the average
number of iterations needed by Algorithm↔B comes to $~\biglp3/(4\ln2)+{1\over2}
\bigrp\sqrt{πm/2}=1.983\sqrt m$. A similar analysis of the more general method
in the answer to exercise 3.1--7 gives $~1.926\sqrt m$, when $p=2.4771$ is
chosen ``optimally'' as the root of $(p↑2-1)\ln p=p↑2-p+1$.]

\ansno 5. $x\mod 3 = 0$; $x \mod 5 = 0$,
1, 4; $x \mod 7 = 0$, 1, 6; $x \mod 8 = 1$, 3, 5, 7; $x > 103$.
The first try is $x = 105$; and $(105)↑2 - 10541 = 484 = 22↑2$. This
would also have been found by Algorithm↔C in a relatively short
time. Thus $10541 = 83 \cdot 127$.

\ansno 6. Let us count the number of solutions
$(x, y)$ of the congruence $N ≡ (x - y)(x + y)\modulo p$,
where $0 ≤ x, y < p$. Since $N \neqv 0$ and $p$ is prime,
$x + y \neqv 0$. For each $v \neqv 0$ there is a unique
$u$ (modulo $p$) such that $N ≡ uv$. The congruences $x - y
≡ u$, $x + y ≡ v$ now uniquely determine $x\mod p$ and $y\mod
p$, since $p$ is odd. Thus the stated congruence has exactly
$p - 1$ solutions $(x, y)$. If $(x, y)$ is a solution, so is
$(x, p - y)$ if $y ≠ 0$, since $(p - y)↑2 ≡ y↑2$; and if $(x,
y↓1)$ and $(x, y↓2)$ are solutions with $y↓1 ≠ y↓2$, we have
$y↑{2}↓{1} ≡ y↑{2}↓{2}$; hence $y↓1 = p - y↓2$. Thus the number
of different $x$ values among the solutions $(x, y)$ is $(p
- 1)/2$ if $N ≡ x↑2$ has no solutions, or $(p + 1)/2$ if $N
≡ x↑2$ has solutions.

\ansno 7. One procedure is to keep two indices for each modulus,
one for the current word position and one for the current bit
position; loading two words of the table and doing an indexed
shift command will bring the table entries into proper alignment.\xskip
(Many computers have special facilities for such bit manipulation.)

\ansno 8. (We may assume that $N = 2M$
is even.)\xskip The following algorithm uses an auxiliary table $X[1]$,
$X[2]$, $\ldotss$, $X[M]$, where $X[k]$ represents the primality
of $2k + 1$.

\def\\#1. {\yskip\noindent\hangindent 38pt\hbox to 38pt{\hfill\bf#1. }}
\\S1. Set $X[k] ← 1$
for $1 ≤ k ≤ M$. Also set $j ← 1$, $p ← 1$, $p ← 3$, $q ← 4$.\xskip (During
this algorithm $p = 2j + 1$, $q = 2j + 2j↑2$; the integer variables
$j$, $k$, $p$, $q$ may readily be manipulated in index registers.)

\\S2. If $X[j] = 0$, go to S4.
Otherwise output $p$, which is prime, and set $k ← q$.

\\S3. If $k ≤ M$, then set $X[k] ← 0$, $k ← k + p$, and repeat this step.

\\S4. Set $j ← j + 1$, $p ← p + 2$, $q
← q + 2p - 2$. If $j ≤ M$, return to S2.\quad\blackslug

\yskip\noindent A major part of this calculation
could be made noticeably faster if $q$ (instead of $j$) were
tested against $M$ in step S4, and if a new loop were appended
that outputs $2j + 1$ for all remaining $X[j]$ that equal
1, suppressing the manipulation of $p$ and $q$.

Improvements in the efficiency of sieve methods for generating primes are discussed in
exercise 5.2.3--15 and in Section 7.1.

\ansno 9. If $p↑2$ is a divisor of $n$ for some
prime $p$, then $p$ is a divisor of $λ(n)$, but not of $n -
1$. If $n = p↓1p↓2$, where $p↓1 < p↓2$ are primes, then $p↓2
- 1$ is a divisor of $λ(n)$ and therefore $p↓1p↓2 - 1 ≡ 0
\modulo{p↓2 - 1}$. Since $p↓2 ≡ 1$, this means $p↓1 - 1$ is a multiple
of $p↓2 - 1$, contradicting the assumption $p↓1 < p↓2$.\xskip [Values
of $n$ for which $λ(n)$ properly divides $n - 1$ are called
``\α{Carmichael numbers}.'' For example, here are some small Carmichael numbers with
up to six prime factors: $3\cdot11\cdot17$, $5\cdot13\cdot17$, $7\cdot11\cdot13
\cdot41$, $5\cdot7\cdot17\cdot19\cdot73$, $5\cdot7\cdot17\cdot73\cdot89\cdot107
$.]

 \ansno 10. Let $k↓p$ be the order of $x↓p$ modulo $n$, and let
$λ$ be the least common multiple of all the $k↓p$'s. Then $λ$
is a divisor of $n - 1$ but not of any $(n - 1)/p$, so $λ =
n - 1$. Since $x↑{\varphi (n)}↓{p} \mod n = 1$, $\varphi (n)$
is a multiple of $k↓p$ for all $p$, so $\varphi (n) ≥ λ$. But
$\varphi (n) < n - 1$ when $n$ is not prime.\xskip (Another way to
carry out the proof is to construct an element $x$ of order
$n - 1$ from the $x↓p$'s, by the method of exercise↔\hbox{3.2.1.2--15}.)

\anskip\null\penalty1000\vskip-6pt
\vbox{\halign to size{\hbox to 19pt{\hfill\bf#}\tabskip0pt plus100pt⊗
\rt{#}\tabskip10pt⊗\rt{#}⊗\rt{#}⊗\rt{#}⊗\rt{#}⊗\rt{#}⊗$\rt{#}$\tabskip 0pt plus100pt
\cr
11. ⊗$U$\hfill⊗$V$\hfill⊗$A$\hfill⊗$P$\hfill⊗$S$⊗$T$⊗\hbox{Output}\cr
\noalign{\vskip2pt}
⊗1984⊗1⊗0⊗992⊗0⊗---\cr
⊗1981⊗1981⊗1⊗992⊗1⊗1981\cr
⊗1983⊗4⊗495⊗993⊗0⊗1⊗993↑2 ≡+2↑2 \cr
⊗1983⊗991⊗2⊗98109⊗1⊗991\cr
⊗1981⊗4⊗495⊗2⊗0⊗1⊗2↑2 ≡+2↑2 \cr
⊗1984⊗1981⊗1⊗99099⊗1⊗1981\cr
⊗1984⊗1⊗1984⊗99101⊗0⊗1⊗99101↑2 ≡+2↑0 \cr}}
\yskip\noindent The factorization $199 \cdot 991$ is evident from
the first or last outputs. The shortness of the cycle, and the
appearance of the well-known number 1984, are probably just
coincidences.

\ansno 12. The following algorithm makes use of an auxiliary
$(m + 1) \times (m + 1)$ matrix of single-precision integers
$E↓{jk}$, $0 ≤ j, k ≤ m$; a single-precision vector $(b↓0, b↓1,
\ldotss , b↓m)$; and a multiple-precision vector $(x↓0, x↓1,
\ldotss , x↓m)$ with entries in the range $0 ≤ x↓k < N$.

\algstep F1. [Initialize.] Set
$b↓i ← -1$ for $0 ≤ i ≤ m$; then set $j ← 0$.

\algstep F2. [Next solution.] Get the next output
$(x, e↓0, e↓1, \ldotss , e↓m)$ produced by Algorithm↔E\null.\xskip (It is
convenient to regard Algorithms E and↔F as coroutines.)\xskip Set
$k ← 0$.

\algstep F3. [Search for odd.] If $k > m$ go to step
F5. Otherwise if $e↓k$ is even, set $k ← k + 1$ and repeat this
step.

\algstep F4. [Linear dependence?] If $b↓k ≥ 0$, then
set $i ← b↓k$, $x ← (x↓ix)\mod N$, $e↓r ← e↓r + E↓{ir}$ for $0
≤ r ≤ m$; set $k ← k + 1$ and return to F3. Otherwise set $b↓k
← j$, $x↓j ← x$, $E↓{jr} ← e↓r$ for $0 ≤ r ≤ m$; set $j ← j + 1$
and return to F2.\xskip (In the latter case we have a new linearly
independent solution, modulo 2, whose first odd component is
$e↓k$.)

\algstep F5. [Try to factor.] (Now $e↓0$, $e↓1$, $\ldotss$,
$e↓m$ are even.)\xskip Set
$$y ← \biglp (-1) ↑{e↓0/2}p↑{e↓1/2}↓{1} \ldotss p↑{e↓m/2}↓{m}\bigrp
\mod N.$$
If $x = y$ or if $x + y = N$, return
to F2. Otherwise compute $\gcd(x - y, N)$, which is a proper
factor of $N$, and terminate the algorithm.\quad\blackslug

\yyskip\noindent It can be shown that this
algorithm finds a factor, whenever it is possible to deduce one from the
given outputs of Algorithm↔E.\xskip[{\sl Proof:} Let the outputs of
Algorithm↔E be $(X↓i,E↓{i0},\ldotss,E↓{im})$ for $1≤i≤t$, and suppose that we
could find a factorization $N=N↓1N↓2$ when $x≡X↓1↑{a↓1}\ldotss X↓t↑{a↓t}$ and
$y≡(-1)↑{e↓0/2}p↓1↑{e↓1/2}\ldotss p↓m↑{e↓m/2}\modulo N$, where $e↓j=
a↓1E↓{1j}+\cdots+a↓tE↓{tj}$ is even for all $j$. Then $x≡\pm y\modulo{N↓1}$
and $x≡\mp y\modulo{N↓2}$. It is not difficult to see that this solution can
be transformed into a pair $(x,y)$ that appears in step↔F5, by a series of
steps that systematically replace $(x,y)$ by $(xx↑\prime,yy↑\prime)$ where $x↑\prime≡
\pm y↑\prime\modulo N$.]

\ansno 13. There are $2↑d$ values of $x$ having the same exponents $(e↓0,\ldotss,
e↓m)$, since we can choose the sign of $x$ modulo↔$q↓i↑{f↓i}$ arbitrarily when
$N=q↓1↑{f↓1}\ldotss q↓d↑{f↓d}$. Exactly two of these $2↑d$ values will fail to
yield a factor.

\ansno 14. Since $P↑2 ≡ kNQ↑2\modulo p$ for any prime divisor
$p$ of $V$, we have $1 ≡ P↑{2(p-1)/2} ≡ (kNQ↑2)↑{(p-1)/2} ≡
(kN)↑{(p-1)/2}\modulo p$, if $P \neqv 0$.
%folio 794 galley 11a (C) Addison-Wesley 1978	*
\ansno 15. $U↓n = (a↑n - b↑n)/\sqrt{D}$, where $a = {1\over
2}(P + \sqrt{D})$, $b = {1\over 2}(P - \sqrt{D})$, $D = P↑2 - 4Q$.
Then $2↑{n-1}U↓n = \sum ↓k{n\choose 2k+1}P↑{n-2k-1}D↑k$; so
$U↓p ≡ D↑{(p-1)/2}\modulo p$ if $p$ is an odd prime. Similarly,
if $V↓n = a↑n + b↑n = U↓{n+1} - QU↓{n-1}$, then $2↑{n-1}V↓n
= \sum ↓k {n\choose 2k}P↑{n-2k}D↑k$, and $V↓p ≡ P↑n ≡ P$. Thus
if $U↓p ≡ -1$, we find that $U↓{p+1}\mod p = 0$. If $U↓p ≡
1$, we find that $(QU↓{p-1})\mod p = 0$; here if $Q$ is a multiple
of $p$, $U↓n ≡ P↑{n-1}\modulo p$ for $n > 0$, so $U↓n$ is
never a multiple of $p$; if $Q$ is not a multiple of $p$, $U↓{p-1}
\mod p = 0$. Therefore as in Theorem↔L\null, $U↓t\mod N = 0$ if
$N = p↑{e↓1}↓{1} \ldotss p↑{e↓r}↓{r}$, $\gcd(N, Q) = 1$, and $t
=\lcm↓{1≤j≤r}\biglp p↑{e↓j-1}↓{j}(p↓j + ε↓j)\bigrp $. Under
the assumptions of this exercise, the rank of apparition of
$N$ is $N + 1$; hence $N$ is prime to $Q$ and $t$ is a multiple
of $N + 1$. Also, the assumptions of this exercise imply that
each $p↓j$ is odd and each $ε↓j$ is $\pm 1$, so $t ≤ 2↑{1-r}\prod p↑{e↓j-1}↓{j}(p↓j
+ {1\over 3}p↓j) = 2({2\over 3})↑rN$; hence $r = 1$ and $t =
p↑{e↓1}↓{1} + ε↓1p↑{e↓1-1}↓{1}$. Finally, therefore, $e↓1 = 1$
and $ε↓1 = 1$.

{\sl Note:} If this test for primality
is to be any good, we must choose $P$ and $Q$ in such a way that
the test will probably work. Lehmer suggests taking
$P = 1$ so that $D = 1 - 4Q$, and choosing $Q$ so that $\gcd(N,
QD) = 1$.\xskip (If the latter condition fails, we know already that
$N$ is not prime, unless $|QD| ≥ N$.)\xskip Furthermore, the derivation
above shows that we will want $ε↓1 = 1$, that is, $D↑{(N-1)/2}
≡ -1\modulo N$. This is another condition that determines
the choice of $Q$. Furthermore, if $D$ satisfies this condition,
and if $U↓{N+1}\mod N ≠ 0$, we know that $N$ is {\sl not}
prime.

{\sl Example:} If $P = 1$ and $Q = -1$, we have
the \α{Fibonacci sequence}, with $D = 5$. Since $5↑{11} ≡ -1 \modulo
{23}$, we might attempt to prove that 23 is prime by using the
Fibonacci sequence:
$$\langle F↓n\mod 23\rangle = 0, 1, 1, 2, 3, 5, 8, 13, 21,
11, 9, 20, 6, 3, 9, 12, 21, 10, 8, 18, 3, 21, 1, 22, 0,\ldotss,$$
so 24 is the rank of apparition of 23
and the test works. However, the Fibonacci sequence cannot be
used in this way to prove the primality of 13 or 17, since $F↓7
\mod 13 = 0$ and $F↓9\mod 17 = 0$. When $p ≡ \pm 1\modulo{10}$,
we have $5↑{(p-1)/2}\mod p = 1$, so $F↓{p-1}$ (not $F↓{p+1}$)
is divisible by $p$.

\ansno 17. Let $f(q) = 2\lg q - 1$. When $q = 2$ or 3, the
tree has at most $f(q)$ nodes. When $q > 3$ is prime, let $q
= 1 + q↓1 \ldotsm q↓t$ where $t ≥ 2$ and $q↓1$, $\ldotss$, $q↓t$
are prime. The size of the tree is $≤1 + \sum f(q↓k) = 2 + f(q
- 1) - t < f(q)$.\xskip [{\sl SIAM J. Computing \bf 7} (1975), \hbox{214--220}.]

\ansno 18. $x\biglp G(α) - F(α)\bigrp$ is the number of $n ≤
x$ whose second-largest prime factor is $≤x↑α$ and whose largest
prime factor is $>x↑α$. Hence$$xG↑\prime (t)\,dt = \biglp π(x↑{t+dt})
- π(x↑t)\bigrp\cdot x↑{1-t}\biglp G\biglp t/(1 - t)\bigrp - F\biglp t/(1
- t)\bigrp\bigrp.$$ The probability that $p↓{t-1} ≤ \sqrt{\chop to 0pt{p↓t}}$ is
$\int ↑{1}↓{0} F\biglp t/2(1 - t)\bigrp t↑{-1}\,dt$.\xskip
[Curiously, it can be shown that this
also equals $\int ↑{1}↓{0} F\biglp t/(1 - t)\bigrp\,dt$, the
average value of $\log p↓t/\!\log x$, and it also equals \α{Golomb's constant} $λ$
of exercises 1.3.3--23 and 3.1--13. The derivative $G↑\prime
(0)$ can be shown to equal $\int ↑{1}↓{0} F\biglp t/(1 - t)\bigrp
t↑{-2}\,dt = F(1) + 2F({1\over 2}) + 3F({1\over 3}) +\cdots
= e↑\gamma$. The third-largest prime factor has $H(α
) = \int ↑{α}↓{0} \biglp H\biglp t/(1 - t)\bigrp - G\biglp t/(1 - t)\bigrp\bigrp
t↑{-1}\,dt$ and $H↑\prime(0) = ∞$. See P. \α{Billingsley}, {\sl Period.\ Math.\
Hungar.\ \bf2} (1972), 283--289; J. \α{Galambos}, {\sl Acta Arith.\ \bf31} (1976),
213--218; D. E. \α{Knuth} and L. \α{Trabb Pardo},
{\sl Theoretical Comp.\ Sci.\ \bf3} (1976), 321--348.]

\ansno 19. $M = 2↑D - 1$ is a multiple of all $p$ for which
the order of 2 modulo $p$ divides $D$. To extend this idea, let $a↓1 = 2$
and $a↓{j+1}
= a↑{q↓j}↓{j}\mod N$, where $q↓j = p↑{e↓j}↓{j}$, $p↓j$ is the
$j$th prime, and $e↓j = \lfloor \log 1000/\!\log p↓j\rfloor $;
let $A = a↓{169}$. Now compute $b↓q =\gcd(A↑q - 1, N)$ for
all primes $q$ between $10↑3$ and $10↑5$. One way to do this is
to start with $A↑{1009}\mod N$ and then to multiply alternately
\inx{MIX (actually 1009)}
by $A↑4\mod N$ and $A↑2\mod N$.\xskip (A similar method was used
in the 1920s by D. N. Lehmer, but he didn't publish it.)\xskip As
\inx{Lehmer, D. N.}
with Algorithm↔B we can avoid most of the gcd's by batching;
e.g., since $b↓{30r-k} =\gcd(A↑{30r} - A↑k, N)$, we might try
batches of\penalty1000\ 8, computing $c↓r = (A↑{30r} - A↑{29})(A↑{30r} -
A↑{23}) \ldotsm (A↑{30r} - A)\mod N$, then $\gcd(c↓r, N)$ for
$33 < r ≤ 3334$.

\ansno 22. Algorithm P fails only when the random
number $x$ does not reveal the fact that $n$ is nonprime. 
Say $x$ is {\sl bad\/} if $x↑q\mod n=1$ or
if one of the numbers $x↑{2↑jq}$ is $≡-1\modulo n$ for $0≤j<k$. Since 1 is bad,
we have $p↓n=(b↓n-1)/(n-2)<b↓n/(n-1)$, where $b↓n$ is the number of bad $x$
such that $1≤x<n$, when $n$ is not prime.

Every bad $x$ satisfies $x↑{n-1}≡1\modulo n$. When $p$ is prime, the number of
solutions to the congruence $x↑q≡1\modulo{p↑e}$ for $1≤x≤p↑e$ is the number of
solutions of $qy≡0$ $\biglp$\hbox{modulo}\penalty1000\ $p↑{e-1}(p-1)\bigrp$
for $0≤y<p↑{e-1}(p-1)$, namely $\gcd\biglp q,p↑{e-1}(p-1)\bigrp$, since we
may replace $x$ by $a↑y$ where $a$ is a primitive root.

Let $n=n↓1↑{e↓1}\ldotss n↓r↑{e↓r}$, where the $n↓i$ are distinct primes. According
to the
Chinese remainder theorem, the number of solutions to the congruence
$x↑{n-1}≡1\modulo n$ is
$\prod↓{1≤i≤r}\gcd\biglp n-1,n↓i↑{e↓i-1}(n↓i-1)\bigrp$, and this is at most
$\prod↓{1≤i≤r}(n↓i-1)$ since $n↓i$ is relatively prime to $n-1$. If
some $e↓i>1$, we have $n↓i-1≤{2\over9}n↓i↑{e↓i}$, hence the number of solutions
is at most ${2\over9}n$; in this case $b↓n≤{2\over9}n≤{1\over4}(n-1)$, since
$n≥9$.

Therefore we may assume that $n$ is the product $n↓1\ldotsm n↓r$ of distinct
primes. Let $n↓i=1+2↑{k↓i}q↓i$, where $k↓1≤\cdots≤k↓r$. Then $\gcd(n-1,n↓i-1)
=2↑{k↑\prime↓i}q↑\prime↓i$, where $k↑\prime↓i=\min(k,k↓i)$ and $q↑\prime↓i=
\gcd(q,q↓i)$. Modulo $n↓i$, the number of $x$ such that $x↑q≡1$ is $q↑\prime↓i$;
and the number of $x$ such that $x↑{2↑jq}≡-1$ is $2↑jq↓i↑\prime$ for
$0≤j<k↓i↑\prime$, otherwise 0. Since $k≥k↓1$, we have $b↓n=q↓1↑\prime\ldotsm
q↓r↑\prime\,\biglp1+\sum↓{0≤j<k↓1}2↑{jr}\bigrp$.

To complete the proof, it suffices to show that $b↓n≤{1\over4}q↓1\ldotsm q↓r
2↑{k↓1+\cdots+k↓r}={1\over4}\varphi(n)$, since $\varphi(n)<n-1$. We have
$$\eqalign{\textstyle\biglp1+\sum↓{0≤j<k↓1}2↑{jr}\bigrp\hbox{\:a/}2↑{k↓1+\cdots+k↓r}
⊗\textstyle≤
\biglp1+\sum↓{0≤j<k↓1}2↑{jr}\bigrp\hbox{\:a/}2↑{k↓1r}\cr⊗=1/(2↑r-1)+
(2↑r-2)\hbox{\:a/}\biglp2↑{k↓1r}(2↑r-1)\bigrp≤1/2↑{r-1},\cr}$$
so the result follows
unless $r=2$ and $k↓1=k↓2$. If $r=2$, exercise↔9 shows that $n-1$ is not a
multiple of both $n↓1-1$ and $n↓2-1$. Thus if $k↓1=k↓2$ we cannot have both
$q↓1↑\prime=q↓1$ and $q↓2↑\prime=q↓2$; it follows that $q↓1↑\prime q↓2↑\prime
≤{1\over3}q↓1q↓2$ and $b↓n≤{1\over6}\varphi(n)$ in this case.

\yyskip [{\sl Reference: J. Number Theory} (1980), to appear.
The above proof shows that $p↓n$ is near $1\over 4$ in only two cases, when $n=
(1+2q↓1)(1+4q↓1)$ or $(1+2q↓1)(1+2q↓2)(1+2q↓3)$. For example, when $n=
49939\cdot99877$ we have $b↓n={1\over4}(49938\cdot99876)$ and $p↓n\approx
.2499925$. See the next answer for further remarks.]

\ansno 23. (a)\9 The proofs are simple except perhaps for the reciprocity law.
Let $p=p↓1\ldotsm p↓s$ and $q=q↓1\ldotsm q↓r$, where the $p↓i$ and $q↓j$ are
prime. Then
$$\bigglp{p\over q}\biggrp=\prod↓{i,j}\bigglp{p↓i\over q↓j}\biggrp
=\prod↓{i,j}(-1)↑{(p↓i-1)(q↓j-1)/4}\,\bigglp{q↓j\over p↓i}\biggrp=
(-1)↑{\vcenter{\hbox{\:b\char6}}↓{i,j}
(p↓i-1)(q↓j-1)/4}\,\bigglp{q\over p}\biggrp,$$
so we need only verify that $\sum↓{i,j\,}(p↓i-1)(q↓j-1)/4≡(p-1)(q-1)/4\modulo 2$.
But $\sum↓{i,j\,}(p↓i-1)(q↓j-1)/4=\biglp\sum↓i(p↓i-1)/2\bigrp\biglp\sum↓j
(q↓j-1)/2\bigrp$ is odd iff an odd number of the $p↓i$ and an odd number of the
$q↓j$ are $≡3\modulo 4$, and this holds iff $(p-1)(q-1)/4$ is odd.

\def\\#1{\raise 2pt\hbox{$\scriptstyle#1$}}
(b) As in exercise↔22, we may assume that $n=n↓1\ldotsm n↓r$ where the $n↓i=1+
2↑{k↓i}q↓i$ are distinct primes, and $k↓1≤\cdots≤k↓r$;
we let $\gcd(n-1,n↓i-1)=2↑{k↑\prime↓i}q↑\prime↓i$ and we call
$x$ {\sl bad} if it falsely makes $n$ look prime. Let $\Pi↓n=\prod↓{1≤i≤r}
q↓i↑\prime\,2↑{\min(k↓i,k-1)}$ be the number of solutions of $x↑{(n-1)/2}≡1$.
The number of bad $x$ with $({\\x\over n})=1$ is $\Pi↓n$, times an extra factor
of $1\over2$ if $k↓1<k$.\xskip (This factor $1\over2$ is needed to
ensure that $({\\x\over n↓i})=-1$ 
for an even number of the $n↓i$ with $k↓i<k$.)\xskip
The number of bad $x$ with $({\\x\over n})=-1$ is $\Pi↓n$ if $k↓1
=k$, otherwise 0.\xskip[If $x↑{(n-1)/2}≡-1\modulo{n↓i}$, we have $({\\x\over
n↓i})=-1$ if $k↓i=k$, $({\\x\over n↓i})=+1$ if $k↓i>k$, and a contradiction if
$k↓i<k$. If $k↓1=k$, there are an odd number of $k↓i$ equal to
$k$.]

{\sl Notes:} The probability of a 
bad guess is $>{1\over4}$ only if $n$ is a \α{Carmichael
number} with $k↓r<k$; for example, $n=7\cdot13\cdot19=1729$,
a number made famous by \α{Ramanujan} in another context. 
Louis \α{Monier} has extended the above analyses to obtain the following closed
formulas for the number of bad $x$ in general:
$$\eqalign{b↓n⊗=\bigglp1+{2↑{rk↓1}-1\over2↑r-1}\biggrp\prod↓{1≤i≤r}q↓i↑\prime;\cr
b↓n↑\prime⊗=\delta↓n\prod↓{1≤i≤r}\gcd\left({n-1\over2},\;n↓i-1\right).\cr}$$
Here $b↓n↑\prime$ is the number of bad $x$ in this exercise, and $\delta↓n$ is
either 2 (if $k↓1=k$), or $1\over2$ (if $k↓i<k$ and $e↓i$ is odd for some $i$), or
1 (otherwise).

(c) If $x↑q\mod n=1$, then $1=({\\x↑q\over n})=({\\x\over n})↑q=({\\x\over n})$.
If $x↑{2↑jq}≡-1\modulo n$, then the order of $x$ modulo $n↓i$ must be an odd multiple
of $2↑{j+1}$ for all prime divisors $n↓i$ of↔$n$. Let $n=n↓1↑{e↓1}\ldotss n↓r↑{e↓r}$
and $n↓i=1+2↑{j+1}q↓i↑{\prime\prime}$; then $({\\x\over n↓i})=(-1)↑{q↓i↑{\prime
\prime}}$, so $({\\x\over n})=+1$ or $-1$ according as $\sum e↓iq↓i↑{\prime\prime}$
is even or odd. Since $n≡\biglp1+2↑{j+1}\sum e↓iq↓i↑{\prime\prime}\bigrp
\modulo{2↑{j+2}}$, the sum $\sum e↓iq↓i↑{\prime\prime}$ is odd iff $j+1=k$.\xskip
[Univ.\ de Paris-Sud, Lab.\ Rech.\ Informatique, Rapport 20 (1978).]

\ansno 24. Let $M↓1$ be a matrix having one row for each nonprime odd number in the
range $1≤n≤N$
and having $N-1$ columns numbered from 2 to $N$; 
the entry in row↔$n$ column $x$ is 1 if $n$ passes the $x$ test of
Algorithm↔P\null, otherwise it is zero. When $N=qn+r$ and $0≤r<n$, we 
know that row $n$ contains at most ${1\over4}qn+\min\biglp{1\over4}n,r\bigrp=
{1\over4}N+\min\biglp{1\over4}n-{1\over4}r,{3\over4}r\bigrp≤{1\over4}N+{3\over16}n
<{1\over2}N$ entries equal to 0, so at least
half of the entries in the matrix are 1. Thus, some column $x↓1$ of $M↓1$ has
at least half of its entries equal to 1. Removing column $x↓1$ and all rows in
which this column contains 1 leaves a matrix $M↓2$ having similar properties; a
repetition of this construction produces matrix $M↓r$ with $N-r$ columns and
fewer than $N↓{\null}/2↑r$ rows, and with
at least ${1\over2}(N-1)$ entries per row equal to 1.\xskip
[Cf.\ {\sl Proc.\ IEEE Symp.\
Foundations of Comp.\ Sci.\ \bf19} (1978), 78.]

[A similar proof implies the existence of a {\sl single} infinite
sequence $x↓1<x↓2<\cdots$ such that the number $n>1$ is prime if and only if it
passes the $x$ test of Algorithm↔P for $x=x↓1$, $\ldotss$, $x=x↓m$, where $m=
{1\over2}\lfloor\lg n\rfloor\biglp\lfloor\lg n\rfloor-1\bigrp$. Does there exist a
sequence $x↓1<x↓2<\cdots$ having this property but with $m=O(\log n)$?]

\ansno 25. This theorem was first proved rigorously by \α{von Mangoldt}
[{\sl J. f\"ur die reine und angew.\ Math.\ \bf114} (1895), 255--305], who
showed in fact that the $O(1)$ term is equal to ${1\over2}\hbox{($x$ is prime)}+
\hbox{constant}+\int↓x↑∞ dt/(t↑2-1)t\ln t$. The constant is 
\inx{logarithmic integral}
$\mathop{\hbox{li}}2-\ln2=\gamma+\ln\ln2+\sum↓{n≥2}(\ln2)↑n/nn!=
0.35201$ 65995 57547 47542 73567 67736 $43657-$.

\ansno 26. If $N$ is not prime, it has a prime factor $q≤\sqrt N$. By hypothesis,
every prime divisor $p$ of $f$ has an integer $x↓p$ such that the order of
$x↓p$ modulo $q$ is a divisor of $N-1$ but not of $(N-1)/p$. Therefore if
$p↑k$ divides $f$, the order of $x↓p$ modulo $q$ is a multiple of↔$p↑k$.
Exercise 3.2.1.2--15 now tells us that there is an element $x$ of order
$f$ modulo↔$q$. But this is impossible, since it implies that $q↑2≥(f+1)↑2≥
(f+1)\,r≥N$, and equality cannot hold.\xskip[{\sl AMM \bf64} (1957), 703--710.]

\ansno 27. If $k$ is not divisible by 3 and if $k≤2↑n+1$, the number $k{\cdot}2↑n
+1$ is prime iff $3↑{2↑{n-1}k}≡-1\modulo{k{\cdot}2↑n+1}$. For if this condition
holds, $k{\cdot}2↑n+1$ is prime by exercise↔26; and if $k{\cdot}2↑n+1$ is prime,
the number 3 is a quadratic nonresidue mod $k{\cdot}2↑n+1$ by the law of
\α{quadratic reciprocity}, since $k{\cdot}2↑n+1\mod12=5$.\xskip
[This test was stated without proof by Proth in {\sl Comptes Rendus \bf87}
(Paris, 1878), 926.]

To implement Proth's test with the necessary efficiency, we need to be able to
\inx{multiplication modulo m}
compute $x↑2\mod(k{\cdot}2↑n+1)$ with about the same speed as we can compute
the quantity
$x↑2\mod(2↑n-1)$. Let $x↑2=A{\cdot}2↑n+B$ and let $A=qk+r$ where $0≤r<k$;
we can determine $q$ and $r$ rapidly, when $k$ is a single-precision number.
Then $x↑2≡{B-q+r{\cdot}2↑n}\modulo{k{\cdot}2↑n+1}$, so the remainder is
easily obtained.

[To test numbers of the form $3{\cdot}2↑n+1$ for primality, the job is only
slightly more difficult; we first try random single-precision numbers until
finding one that is a quadratic nonresidue mod $3{\cdot}2↑n+1$ by the law of
quadratic reciprocity, then use this number in place of ``3'' in the above test.
If $n\mod4≠0$, the number 5 can be used. It turns out that $3{\cdot}2↑n+1$ is
prime when $n=1$, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353,
408, 438, 534, 2208, 2816, 3168, 3189, 3912;
and $5{\cdot}2↑n+1$ is prime when $n=1$, 3, 7, 13, 15, 25, 39,
55, 75, 85, 127, 1947. See R.↔M. \α{Robinson}, {\sl Proc.\ Amer.\ Math.\ Soc.\
\bf9} (1958), 673--681; the additional numbers listed here
were found by M.↔F. \α{Plass}.]

\ansno 28. $f(p, p↑2d) = 2/(p + 1) + f(p, d)/p$, since $1/(p
+ 1)$ is the probability that $A$ is a multiple of $p$.\xskip $f(p,
pd) = 1/(p + 1)$ when $d\mod p ≠ 0$.\xskip $f(2, 4k + 3) = {1\over
3}$ since $A↑2 - (4k + 3)B↑2$ cannot be a multiple of 4; $f(2,
8k + 5) = {2\over 3}$ since $A↑2 - (8k + 5)B↑2$ cannot be a
multiple of 8; $f(2, 8k + 1) = {1\over 3} + {1\over 3} + {1\over
3} + {1\over 6} + {1\over 12} +\cdots = {4\over 3}$.\xskip
$f(p, d) = \biglp2p/(p↑2 - 1), 0\bigrp$ if $d↑{(p-1)/2}\mod p =
(1, p - 1)$, respectively, for odd $p$.

\ansno 29. The number of solutions to the equation $x↓1+\cdots+x↓m≤r$ in
nonnegative integers $x↓i$ is ${m+r\choose r}≥m↑r/r!$, and each of these
corresponds to a unique integer ${p↓1↑{x↓1}\ldotss p↓m↑{x↓m}≤n}$.\xskip[For sharper
estimates, in the special case that $p↓j$ is the $j$th prime for all $j$, see N. G.
\α{de Bruijn}, {\sl Indag.\ Math.\ \bf28} (1966), 240--247; H. \α{Halberstam},
{\sl Proc. London Math.\ Soc.\ \rm(3) \bf21} (1970), 102--107.]

\ansno 30. If $p↓1↑{e↓1}\ldotss p↓m↑{e↓m}≡x↓i↑2\modulo{q↓i}$, we can find $y↓i$
such that $p↓1↑{e↓1}\ldotss p↓m↑{e↓m}≡(\pm y↓i)↑2\modulo{q↓i↑{d↓i}}$, hence
by the Chinese remainder theorem we obtain $2↑d$ values of $X$ such that $X↑2≡
p↓1↑{e↓1}\ldotss p↓m↑{e↓m}\modulo N$. Such $(e↓1,\ldotss,e↓m)$ correspond to at
most $r\choose r/2$ pairs $(e↓1↑\prime,\ldotss,e↓m↑\prime;
e↓1↑{\prime\prime},\ldotss,e↓m↑{\prime\prime})$ having the hinted properties.
Now for each of the $2↑d$ binary numbers $a=(a↓1\ldotsm a↓d)↓2$, let $n↓a$ be
the number of exponents $(e↓1↑\prime,\ldotss,e↓m↑\prime)$ such that
$(p↓1↑{e↓1↑\prime}\ldotss p↓m↑{e↓m↑\prime})↑{(q↓i-1)/2}≡(-1)↑{a↓i}\modulo{q↓i}$;
we have proved that the required number of integers $X$ is $≥2↑d\biglp\sum↓a
n↓a↑2\bigrp\vcenter{\hbox{\:@\char'16}}{r\choose r/2}$. Since $\sum↓a n↓a$ is
the number of ways to choose at most $r/2$ objects from a set of $m$ objects
\inx{combinations with repetitions}
with repetitions permitted, namely $m+r/2\choose r/2$, we have $\sum↓an↓a↑2≥
{m+r/2\choose r/2}↑2/2↑d≥m↑r\vcenter{\hbox{\:@\char'16}}\biglp2↑d(r/2)!\bigrp$.\xskip
[Cf.\ {\sl J. Number Theory}, to appear.]

\ansno 31. Set $r=M$, $qM=4m$, $εM=2m$.

\def\\{\spose{\raise4.5pt\hbox{\hskip2.3pt$\scriptscriptstyle3$}}\sqrt N}
\ansno 32. Let $M=\lfloor\\\rfloor$, and let the places $x↓i$ of each message
be restricted to the range $0≤x<M↑3-M↑2$. If $x≥M$, encode it as $x↑3\mod N$ as
before, but if $x<M$ change the encoding to $(x+yM)↑3\mod N$, where $y$ is a
random number in the range $M↑2-M≤y≤M↑2$. To decode, first take the cube root;
\inx{random numbers, using}
and if the result is $M↑3-M↑2$ or more, take the remainder mod $M$.

\ansno 34. Let $P$ be the probability that $x↑m\mod p=1$ and let $Q$ be
the probability
that $x↑m\mod q=1$. The probability that $\gcd(x↑{m\!}-1,N)=p$ or $q$ is ${P(1\!-\!Q)+
Q(1\!-\!P)}=P+Q-2PQ$. If $P≤{1\over2}$ or $Q≤{1\over2}$, this probability is
$≥{1\over2}\max(P,Q)≥{1\over2}10↑{-6}$, so we have a good chance of finding a
factor after about $10↑6\log m$ arithmetic operations modulo↔$N$. On the other
hand if $P>{1\over2}$ and $Q>{1\over2}$ then $P\approx Q\approx1$, since we have
the general formula $P=\gcd(m,p-1)/p$; thus $m$ is a multiple of lcm$(p-1,q-1)$
in this case. Let $m=2↑kr$ where $r$ is odd, and form the sequence $x↑r\mod N$,
${x↑{2r}\mod N}$, $\ldotss$, $x↑{2↑kr}\mod N$; with high probability we find
that the first appearance of 1 is preceded 
by a value $y$ other than $N-1$, as in
Algorithm↔P, hence $\gcd(y-1,N)=p$ or↔$q$.

\ansno 35. Let $f=(p↑{q-1}-q↑{p-1})\mod N$. Since $p\mod4=q\mod4=3$,
we have $({-1\over p})=({-1\over q})=({f\over p})=-({f\over q})=-1$, and we also
have $({2\over p})=-({2\over q})=1$. Given a message $x$ in the range
$0≤x≤{1\over8}(N-5)$, let $\=x=4x+2$ or $8x+4$, whichever satisfies
$({\=x\over N})=1$; then transmit the message $\=x↑2\mod N$.

 To decode this message, we first use a SQRT box to find the unique number $y$
such that $y↑2≡\=x↑2\mod N$ and $({y\over N})=1$ and $y$ is even. Then $y=\=x$,
since the other three square roots of $\=x↑2$ are $N-\=x$ and $(\pm f\=x)\mod N$;
the first of these is odd, and the other two have negative Jacobi symbols. The
decoding is now completed by setting $x=\lfloor y/4\rfloor$ if $y\mod4=2$,
otherwise $x←\lfloor y/8\rfloor$.

Anybody who can decode such encodings can also find the factors of $N$, because
the decoding of a false message $\=x↑2\mod N$ when $({\=x\over N})=-1$ reveals
$(\pm f)\mod N$, a number that has a nontrivial gcd with $N$.
% To appear

\ansno 36. The $m$th \α{prime} equals
$$m\ln m+m\ln\ln m-m+m\ln\ln m/\!\ln m-2m/\!\ln m+O\biglp
m(\log\log m)↑2(\log m)↑{-2}\bigrp,$$by (4), although for this problem we
need only the weaker estimate $p↓m=m\ln m+O(m\log\log m)$.\xskip(We will assume that
\inx{prime number theorem}
$p↓m$ is the $m$th prime, since this corresponds to the assumption that
$V$ is uniformly distributed.)\xskip If we choose $\ln m={1\over2}c\sqrt{
\,\ln N\ln\ln N}$, where $c=O(1)$, we find that $r=c↑{-1}\sqrt{\,\ln N/\!\ln\ln N}
-c↑{-2}-c↑{-2}(\ln\ln\ln N/\!\ln\ln N)-2c↑{-2}(\ln{1\over2}c)/\!\ln\ln N+
O(\sqrt{\,\ln\ln N/\!\ln N}\,)$. The estimated running time (21) now
simp\-lifies somewhat surprisingly to the formula $\exp\biglp f(c,N)\sqrt{\,
\ln N\ln\ln N}+O(\log\log N)\bigrp$, where we have
$f(c,N)=c+\biglp1-(1+\ln2)/\!\ln\ln N\bigrp
c↑{-1}$. The value of $c$ that minimizes $f(c,N)$ is $\sqrt{1-(1+\ln2)/\!\ln\ln N}$,
so we obtain the estimate$$\textstyle
\exp\biglp2\sqrt{\,\ln N\ln\ln N}\sqrt{1-(1+\ln2)/\!
\ln\ln N}+O(\log\log N)\bigrp.$$When $N=10↑{50}$ this gives $ε(N)
\approx.33$, which is still much larger than the observed behavior.

{\sl Note:} The partial quotients of $\sqrt D$ seem to behave according to the
distribution obtained for random real numbers in Section↔4.5.3. For example, the
first million partial quotients of the number $10↑{18}+314159$ include exactly
(415236, 169719, 93180, 58606) cases where $A↓n$ is respectively $(1,2,3,4)$. Since
$V↓n$ lies between $(\sqrt D+1)/(A↓n+1)$ and $2\sqrt D/A↓n$, it is likely that
$V↓n≤2\sqrt D y$ with probability about $\lg(1+y)$. This is not much different
from a uniform distribution, so something besides the size of $V↓n$ must account
for the unreasonable effectiveness of Algorithm↔E.

\ansno 37. Apply exercise 4.5.3--12 to the number $\sqrt D+R$, to see that the
periodic part begins immediately, and run the period backwards to verify the
palindromic property.\xskip[It follows that the second half of the period gives
the same $V$'s as the first, and Algorithm↔E could be shut down earlier by
terminating it when $U=U↑\prime$ or $V=V↑\prime$ in step↔E5. However, the period
is generally so long, we never even get close to halfway through it, so there is
no point in making the algorithm more complicated.]

\chpar7←1000 % inhibit break after relations, especially "←"
\ansno 38. [{\sl Inf.\ Proc.\ Letters \bf8} (1979), 28--31.]\xskip
Note that $x\mod y=x-y\,\lfloor x/y\rfloor$ can be computed easily on
such a machine, and we can get simple constants like $0=x-x$, $1=\lfloor
x/x\rfloor$, $2=1+1$; we can test $x>0$ by testing whether $x=1$ or $\lfloor
x/(x-1)\rfloor≠0$.

(a)\9 First compute $l=\lfloor\lg n\rfloor$ in $O(\log n)$ steps, by repeatedly
dividing by 2; at the same time compute $k=2↑l$ and $A←2↑{2↑{l+1}}$ in
$O(\log n)$ steps by repeatedly setting $k←2k$, $A←A↑2$. For the main
computation, suppose we know that $t=A↑m$, $u=(A+1)↑m$, and $v=m!$; then
we can increase the value of $m$ by 1 by setting $m←m+1$, $t←At$, $u←(A+1)u$,
$v←vm$; and we can {\sl double} the value of $m$ by setting $m←2m$, $u←u↑2$,
$v←\biglp\lfloor u/t\rfloor\mod A\bigrp v↑2$, $t←t↑2$, provided that $A$ is
sufficiently large.\xskip$\biglp$Consider the number $u$ in radix-$A$ notation;
$A$ must be greater than $2m\choose m$.$\bigrp$\xskip Now if $n=(a↓l\ldotsm a↓0)
↓2$, let $n↓j=(a↓l\ldotsm a↓j)↓2$; if $m=n↓j$ and $k=2↑j$ and $j>0$ we can
decrease $j$ by 1 by setting $k←\lfloor k/2\rfloor$, $m←2m+\biglp\lfloor n/k
\rfloor\mod2\bigrp$. Hence we can compute $n↓j!$ for $j=l$, $l-1$, $\ldotss$,
0 in $O(\log n)$ steps.\xskip[Another solution, due to Julia Robinson, is to
\inx{Robinson, Julia}
compute $n!=\lfloor B↑n/{B\choose n}\rfloor$ when $B>(2n)↑{n+1}$; cf.\
{\sl AMM \bf80} (1973), 250--251, 266.]

(b)\9 First compute $A=2↑{2↑{l+2}}$ as in (a), then find the least $k≥0$ such that
$2↑{k+1}!\mod n=0$. If $\gcd(n,2↑k!)≠1$, let $f(n)$ be this value; note that this
gcd can be computed in $O(\log n)$ steps by Euclid's algorithm. Otherwise we will
find the least integer $m$ such that ${m\choose\lfloor m/2\rfloor}\mod n=0$, and
let $f(n)=\gcd(m,n)$.\xskip$\biglp$Note that in this case $2↑k<m≤2↑{k+1}$,
hence $\lceil m/2\rceil≤2↑k$ and $\lceil m/2\rceil!$ is relatively prime to
$n$; therefore ${m\choose\lfloor m/2\rfloor}\mod n=0$ iff $m!\mod n=0$.
Furthermore $n≠4$.$\bigrp$

To compute $m$ with a bounded number of registers, we can use \α{Fibonacci numbers}
(cf.\ Algorithm 6.2.1F\null). Suppose we know that
$s=F↓j$, $s↑\prime=F↓{j+1}$, $t=A↑{F↓j}$, $t↑\prime=
A↑{F↓{j+1}}$, $u=(A+1)↑{2F↓j}$, $u↑\prime=(A+1)↑{2F↓{j+1}}$, $v=A↑m$,
$w=(A+1)↑{2m}$, ${2m\choose m}\mod n≠0$, and ${2(m+s)\choose m+s}=0$.
It is easy to reach this state of affairs with $m=F↓{j+1}$, for suitably large
$j$, in $O(\log n)$ steps; furthermore $A$ will be larger than $2↑{2(m+s)}$.
If $s=1$, we set $f(n)=\gcd(2m+1,n)$ or $\gcd(2m+2,n)$, whichever is $≠1$,
and terminate the algorithm. Otherwise we reduce $j$ by 1 as follows: Set
$r←s$, $s←s↑\prime-s$, $s←r$, $r←t$, $t←\lfloor t↑\prime/t\rfloor$, $t↑\prime←r$,
$r←u$, $u←\lfloor u↑\prime/u\rfloor$, $u↑\prime←r$; then
if $\biglp\lfloor wu/vt\rfloor \mod A\bigrp\mod n≠0$, set $m←m+s$, $w←wu$, $v←vt$.

[Can this problem be solved with fewer than $O(\log n)$ operations? Can the
smallest, or the largest, prime factor of $n$ be computed in $O(\log n)$
operations?]

\chpar7←50 % restore relbreak penalty
%folio 795 galley 11b (C) Addison-Wesley 1978	*
\ansbegin{4.6}

\ansno 1. $9x↑2 + 7x + 9$;\xskip $5x↑3 + 7x↑2
+ 2x + 6$.

\ansno 2. (a)\9 True.\xskip (b) False if the algebraic
system $S$ contains ``zero divisors,'' nonzero numbers whose
product is zero, as in exercise↔1; otherwise true.\xskip (c) True when $m≠n$, but
false in general when $m=n$, since the leading coefficients might cancel.

\ansno 3. Assume that $r ≤ s$. For $0
≤ k ≤ r$ the maximum is $m↓1m↓2(k + 1)$; for $r ≤ k ≤ s$ it
is $m↓1m↓2(r + 1)$; for $s ≤ k ≤ r + s$ it is $m↓1m↓2(r + s
+ 1 - k)$. The least upper bound valid for all $k$ is $m↓1m↓2(r
+ 1)$.\xskip (The solver of this exercise will know how to factor
the polynomial $x↑7 + 2x↑6 + 3x↑5 + 3x↑4 + 3x↑3 + 3x↑2 + 2x
+ 1$.)

\ansno 4. If one of the polynomials has fewer than
$2↑t$ nonzero coefficients, the product can be formed by putting
exactly $t - 1$ zeros between each of the coefficients, then
multiplying in the binary number system, and finally using a
\α{logical} \.{\α{AND}} operation (present on most binary computers, cf.\
Section 4.5.4) to zero out the extra bits. For example, if $t
= 3$, the multiplication in the text would become $(1001000001)↓2
\times (1000001001)↓2 = (1001001011001001001)↓2$; if we \.{AND}
this result with the constant $(1001001 \ldotsm 1001)↓2$, the desired
answer is obtained. A similar technique can be used to multiply
polynomials with nonnegative coefficients, when it is known that
the coefficients will not be too large.

\ansno 5. Polynomials of degree $≤2n$ can be represented
as $U↓1(x)x↑n + U↓0(x)$ where deg$(U↓1)$ and deg$(U↓0) ≤ n$;
and $\biglp U↓1(x)x↑n + U↓0(x)\bigrp\biglp V↓1(x)x↑n
+ V↓0(x)\bigrp = U↓1(x)V↓1(x)(x↑{2n} + x↑n) + \biglp U↓1(x)
+ U↓0(x)\bigrp\biglp V↓1(x) + V↓0(x)\bigrp x↑n + U↓0(x)V↓0(x)(x↑n
+ 1)$.\xskip (This equation assumes that arithmetic is being done
modulo 2.)\xskip Thus Eqs.\ 4.3.3--3, 4, 5 hold.

{\sl Notes:} S. A. \α{Cook} has shown that Algorithm
4.3.3C can be extended in a similar way, and exercise 4.6.4--57
describes a method requiring even fewer operations for large↔$n$.
But these ideas are not useful for ``sparse'' polynomials
(having mostly zero coefficients).

%folio 796 galley 11c (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hbox{#1}}(}\def\+#1\biglp{\mathop{\hbox{#1}}\biglp}
\ansbegin{4.6.1}

\ansno 1. $q(x) = 1 \cdot 2↑3x↑3 + 0
\cdot 2↑2x↑2 - 2 \cdot 2x + 8 = 8x↑3 - 4x + 8$;\xskip$r(x) = 28x↑2
+ 4x + 8$.

\ansno 2. The monic sequence of polynomials produced
during Euclid's algorithm has the coefficients $(1, 5, 6, 6,
1, 6, 3)$, $(1, 2, 5, 2, 2, 4, 5)$, $(1, 5, 6, 2, 3, 4)$, $(1, 3,
4, 6)$, 0. Hence the greatest common divisor is $x↑3 + 3x↑2 +
4x + 6$.\xskip (The greatest common divisor of a polynomial and its
reverse is always symmetric, in the sense that it is a unit
multiple of its own reverse.)

\ansno 3. The procedure of Algorithm↔4.5.2X is
valid, with polynomials over $S$ substituted for integers. When
the algorithm terminates, we have $U(x) = u↓2(x)$, $V(x) = u↓1(x)$.
Let $m =\\deg(u)$, $n =\\deg(v)$. It is easy to prove by induction
that $\\deg(u↓3) +\\deg(v↓1) = n$, $\\deg(u↓3) +\\deg(v↓2) = m$,
after step X3, throughout the execution of the algorithm, provided
that $m ≥ n$. Hence if $m$ and $n$ are greater than $d =\+deg\biglp
\gcd(u, v)\bigrp$ we have $\\deg(U) < m - d$, $\\deg(V) < n - d$;
the exact degrees are $m - d↓1$ and $n - d↓1$, where $d↓1$ is
the degree of the second-last nonzero remainder. If $d = \min(m,
n)$, say $d = n$, we have $U(x) = 0$ and $V(x) = 1$.

When $u(x) = x↑m - 1$ and $v(x) = x↑n - 1$, the
identity $(x↑m - 1)\mod(x↑n - 1) = x↑{m\mod n} - 1$ shows that
all polynomials occurring during the calculation are monic, with
integer coefficients. When $u(x) = x↑{21} - 1$ and $v(x) = x↑{13}
- 1$, we have $V(x) = x↑{11} + x↑8 + x↑6 + x↑3 + 1$ and $U(x) =
-(x↑{19} + x↑{16} + x↑{14} + x↑{11} + x↑8 + x↑6 + x↑3 + x)$.\xskip
[See also Eq.\ 3.3.3--29, which gives an alternative formula
for $U(x)$ and $V(x)$.]

\ansno 4. Since the quotient $q(x)$ depends only on $v(x)$
and the first $m - n$ coefficients of $u(x)$, the remainder
$r(x) = u(x) - q(x)v(x)$ is uniformly distributed and independent
of $v(x)$. Hence each step of the algorithm may be regarded
as independent of the others; this algorithm is much more well-behaved
than Euclid's algorithm over the integers.

The probability that $n↓1 = n - k$ is $p↑{1-k}(1
- 1/p)$, and $t = 0$ with probability $p↑{-n}$. Each succeeding
step has essentially the same behavior; hence we can see that
any given sequence of degrees $n$, $n↓1$, $\ldotss$, $n↓t$, $-∞$ occurs
with probability $(p - 1)↑t/p↑n$. To find the average value
of $f(n↓1, \ldotss , n↓t)$, let $S↓t$ be the sum of $f(n↓1, \ldotss
, n↓t)$ over all sequences $n > n↓1 >\cdots > n↓t
≥ 0$ having a given value of $t$; then the average is $\sum
↓t S↓t(p - 1)↑t/p↑n$.

Let $f(n↓1, \ldotss , n↓t) = t$; then
$S↓t = {n\choose t}(t + 1)$, so the average is $n(1 - 1/p)$. Similarly,
if $f(n↓1, \ldotss , n↓t) = n↓1 +\cdots + n↓t$, then
$S↓t = {n\choose2}{n-1\choose t-1}$, and the average is ${n\choose2}(1
- 1/p)$. Finally, if $f(n↓1, \ldotss , n↓t) = (n - n↓1)n↓1 +\cdots
+ (n↓{t-1} - n↓t)n↓t$, then $S↓t = {{n+2\choose t+2}
- (n + 1){n+1\choose t+1}}+ {n+1\choose2}{n\choose t}$, and the
average is ${{n+1\choose2} - (n + 1)p/(p - 1)} + {\biglp p/(p -
1)\bigrp ↑2(1 - 1/p↑{n+1})}$.

As a consequence we can see that if $p$ is large
there is very high probability that $n↓{j+1} = n↓j - 1$ for
all $j$.\xskip (If this condition fails over the rational numbers,
it fails for all $p$, so we have further evidence for the text's
claim that Algorithm↔C almost always finds $\delta↓2 =\cdots
= 1$.)

\ansno 5. Using the formulas developed
in exercise↔4, with $f(n↓1, \ldotss , n↓t) = \delta ↓{n↓t0}$,
we find that the probability is $1 - 1/p$ if $n > 0$, 1 if
$n = 0$.

\ansno 6. Assuming that the constant terms $u(0)$
and $v(0)$ are nonzero, imagine a ``right-to-left'' division
algorithm, $u(x) = v(x)q(x) + x↑{m-n}r(x)$, where $\\deg(r) <\\deg(v)$.
We obtain a gcd algorithm analogous to Algorithm↔4.5.2B\null, which
is essentially Euclid's algorithm applied to the ``\α{reverse}''
of the original inputs (cf.\ exercise↔2), afterwards reversing
the answer and multiplying by an appropriate power of $x$.

\ansno 7. The units of $S$ (as polynomials of degree
zero).
%folio 797 galley 12 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hbox{#1}}(}\def\+#1\biglp{\mathop{\hbox{#1}}\biglp}
\ansno 8. If $u(x) = v(x)w(x)$, where $u(x)$ has
integer coefficients while $v(x)$ and $w(x)$ have rational coefficients,
there are integers $m$ and $n$ such that $m\cdot v(x)$ and $n \cdot
w(x)$ have integer coefficients. Now $u(x)$ is primitive, so
we have
$$u(x) = \pm\,\+pp\biglp m \cdot v(x)\bigrp\+pp\biglp n \cdot w(x)\bigrp.$$

\ansno 9. We can extend Algorithm↔E as follows:
Let $\biglp u↓{1\hskip-.35pt}(x), u↓2(x), u↓3, u↓4(x)\bigrp$ and $\biglp v↓
{1\hskip-.35pt}(x),\hskip-1pt
v↓2(x)$, $v↓3, v↓4(x)\bigrp$ be quadruples that satisfy the relations
$u↓1(x)u(x) + u↓2(x)v(x) = u↓3u↓4(x)$, \ $v↓1(x)u(x) + v↓2(x)v(x)
= v↓3v↓4(x)$. The extended algorithm starts with the quadruples $\biglp 1, 0,
\\cont(u), \\pp(u(x))\bigrp$ and $\biglp 0, 1, \\cont(v), \\pp(v(x))\bigrp$
and manipulates them in such a way as to preserve
the above conditions, where $u↓4(x)$ and $v↓4(x)$ run through the
same sequence as $u(x)$ and $v(x)$ do in Algorithm↔E\null. If $au↓4(x)
= q(x)v↓4(x) + br(x)$, we have $av↓3\biglp u↓1(x), u↓2(x)\bigrp
- q(x)u↓3\biglp v↓1(x), v↓2(x)\bigrp = \biglp r↓1(x), r↓2(x)\bigrp
$, where $r↓1(x)u(x) + r↓2(x)v(x) = bu↓3v↓3r(x)$, so the extended
algorithm can preserve the desired relations. If $u(x)$ and
$v(x)$ are relatively prime, the extended algorithm eventually
finds $r(x)$ of degree zero, and we obtain $U(x) = r↓2(x)$, $V(x)
= r↓1(x)$ as desired.\xskip$\biglp$In practice we would divide $r↓1(x)$,
$r↓2(x)$, and $bu↓3v↓3$ by $\gcd\biglp\\cont(r↓1),\\ cont(r↓2)\bigrp$.$\bigrp
$\xskip Conversely, if such $U(x)$ and $V(x)$ exist, then $u(x)$ and
$v(x)$ have no common prime divisors, since they are primitive
and have no common divisors of positive degree.

\ansno 10. By successively factoring reducible polynomials
into polynomials of smaller degree, we must
obtain a finite factorization of any polynomial into irreducibles.
The factorization of the {\sl content} is unique. To show that
there is at most one factorization of the primitive part, the
key result is to prove that if $u(x)$ is an irreducible factor
of $v(x)w(x)$, but not a unit multiple of the irreducible polynomial
$v(x)$, then $u(x)$ is a factor of $w(x)$. This can be proved
by observing that $u(x)$ is a factor of $v(x)w(x)U(x) = rw(x)
- w(x)u(x)V(x)$ by the result of exercise↔9, where $r$ is a
nonzero constant.

\ansno 11. The only row names needed
would be $A↓1$, $A↓0$, $B↓4$,
$B↓3$, $B↓2$, $B↓1$, $B↓0$, $C↓1$, $C↓0$, $D↓0$. In general, let $u↓{j+2}(x)
= 0$; then the rows needed for the proof are $A↓{n↓2-n↓j}$
through $A↓0$, $B↓{n↓1-n↓j}$ through $B↓0$, $C↓{n↓2-n↓j}$ through $C↓0$, 
$D↓{n↓3-n↓j}$ through $D↓0$, etc.

\ansno 12. If $n↓k = 0$, the text's proof of (24) shows that the value of
the determinant is $\pm h↓k$, and this equals $\pm\lscr↓k↑{n↓{k-1}}/
\prod↓{1<j<k}\lscr↓{\!j}↑{\delta↓{j-1}(\delta↓j-1)}$.
If the polynomials have a factor
of positive degree, we can artificially assume that the polynomial
zero has degree zero and use the same formula with $\lscr↓k=
0$.

{\sl Notes:} The value $R(u, v)$ of Sylvester's determinant
is called the {\sl \α{resultant}} of $u$ and↔$v$, and the quantity
$(-1)↑{\hbox{\:e deg}(u)(\hbox{\:e deg}(u)-1)/2}\lscr(u)↑{-1}R(u, u↑\prime )$ is
called the {\sl \α{discriminant}} of↔$u$, where $u↑\prime$ is the derivative of $u$. 
If $u(x)$ has the factored form ${a(x - α↓1)
\ldotsm (x - α↓m)}$, and if $v(x) = b(x - β↓1) \ldotsm (x - β↓n)$,
the resultant $R(u, v)$ is $a↑nv(α↓1) \ldotsm v(α↓m) = (-1)↑{mn}b↑mu(β↓1)
\ldotsm u(β↓n) = a↑nb↑m \prod↓{1≤i≤m,1≤j≤n}(α↓i - β↓j)$. It follows
that the polynomials of degree $mn$ in $y$ defined as the respective
resultants with $v(x)$ of $u(y - x)$, $u(y + x)$, $x↑mu(y/x)$, and $u(yx)$
have as respective roots the sums $α↓i + β↓j$, differences
$α↓i - β↓j$, products $α↓iβ↓j$, and quotients $α↓i/β↓j$ $\biglp$when
$v(0) ≠ 0\bigrp $. This idea has been used by R. G. K.
\α{Loos} to construct algorithms for arithmetic on algebraic numbers
[{\sl SIAM J. Computing}, to appear].

If we replace each row $A↓i$ in Sylvester's matrix by
$$(b↓0A↓i + b↓1A↓{i+1} +\cdots + b↓{n↓2-1-i}A↓{n↓2-1})
- (a↓0B↓i + a↓1B↓{i+1} + \cdots + a↓{n↓2-1-i}B↓{n↓2-1}),$$
and then delete rows $B↓{n↓2-1}$
through $B↓0$ and the last $n↓2$ columns, we obtain an $n↓1
\times n↓1$ determinant for the resultant instead of the original
$(n↓1 + n↓2) \times (n↓1 + n↓2)$ determinant. In some cases
the resultant can be evaluated efficiently by means of this
determinant; see {\sl CACM \bf 12} (1969), 23--30, 302--303.

J. T. \α{Schwartz} has shown that it is possible to evaluate
resultants and \α{Sturm} sequences for
polynomials of degree $n$ with a total of $O\biglp n(\log n)↑2\bigrp$ arithmetic
operations as $n→∞$.\xskip [{\sl JACM}, to appear.]

\ansno 13. One can show by induction on $j$ that the values of $\biglp
u↓{j+1}(x),g↓{j+1},h↓j\bigrp$ are replaced respectively by $\biglp\lscr↑{1+p↓{j\,}}
w(x)u↓j(x),\lscr↑{2+p↓{j\,}}g↓j,\lscr↑{p↓{j\,}}h↓j\bigrp$ for $j≥2$, 
where $p↓j=n↓1+n↓2-2n↓j$.\xskip
[In spite of this growth, the bound (26) remains valid.]

\ansno 14. Let $p$ be a prime of the domain, and let $j,k$ be
maximum such that $p↑k\rslash v↓n = \lscr(v)$, $p↑j\rslash v↓{n-1}$.
Let $P = p↑k$. By Algorithm↔R we may write $q(x) = a↓0 + Pa↓1x
+\cdots + P↑sa↓sx↑s$, where $s = m - n ≥ 2$. Let
us look at the coefficients of $x↑{n+1}$, $x↑n$, and $x↑{n-1}$
in $v(x)q(x)$, namely $Pa↓1v↓n + P↑2a↓2v↓{n-1} +\cdotss$, $a↓0v↓n
+ Pa↓1v↓{n-1} +\cdotss$, and $a↓0v↓{n-1} + Pa↓1v↓{n-2} +\cdotss$,
each of which is a multiple of $P↑3$. We conclude from the first
that $p↑j\rslash a↓1$, from the second that $p↑{\min(k,2j)}\rslash
a↓0$, then from the third that $P\rslash a↓0$. Hence $P\rslash
r(x)$.\xskip [If $m$ were only $n + 1$, the best we could prove would
be that $p↑{\lceil k/2\rceil }$ divides $r(x)$; e.g., consider
$u(x) = x↑3 + 1$, $v(x) = 4x↑2 + 2x + 1$, $r(x) = 18$. On the other hand, an
argument based on determinants of matrices like (21) and (22) can be used to
show that \def\\{\hbox{\:e deg}}$\lscr(r)↑{\\(v)-\\(r)-1}r(x)$ is always a
multiple of $\lscr(v)↑{(\\(u)-\\(v))(\\(v)-\\(r)-1)}$.]
%folio 800 galley 13 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hbox{#1}}(}\def\+#1\biglp{\mathop{\hbox{#1}}\biglp}
\ansno 15. Let $c↓{ij} = a↓{i1}a↓{j1} +\cdots +
a↓{in}a↓{jn}$; we may assume that $c↓{ii} > 0$ for all $i$.
If $c↓{ij} ≠ 0$ for some $i ≠ j$, we can replace row $i$ by
$(a↓{i1} - ca↓{j1}, \ldotss , a↓{in} - ca↓{jn})$, where $c =
c↓{ij}/c↓{jj}$; this does not change the value of the determinant,
and it decreases the value of the upper bound we wish to prove,
since $c↓{ii}$ is replaced by $c↓{ii} - c↑{2}↓{ij}/c↓{ij}$.
These replacements can be done in a systematic way for increasing
$i$ and for $j < i$, until $c↓{ij} = 0$ for all $i ≠ j$.\xskip [The
latter algorithm is called ``\α{Schmidt's orthogonalization process}'';
see {\sl Math.\ Annalen \bf 63} (1907), 442.]\xskip Then $\det(A)↑2
= \det(AA↑T) = c↓{11} \ldotsm c↓{nn}$.

\ansno 16. Let $f(x↓1, \ldotss , x↓n) =
g↓m(x↓2, \ldotss , x↓n)x↑{m}↓{1} +\cdots + g↓0(x↓2,
\ldotss , x↓n)$ and $g(x↓2, \ldotss , x↓n) = g↓m(x↓2, \ldotss
, x↓n)↑2 +\cdots + g↓0(x↓2, \ldotss , x↓n)↑2$; the
latter is not identically zero. We have $$a↓N ≤ m(2N + 1)↑{n-1}
+ (2N + 1)b↓N,$$where $b↓N$ counts the integer solutions
of $g(x↓2, \ldotss , x↓n) = 0$ with variables bounded by↔$N$.
Hence $\lim↓{N→∞} a↓N/(2N + 1)↑n = \lim↓{N→∞} b↓N/(2N + 1)↑{n-1}$,
and this is zero by induction.

\ansno 17. (a)\9 For convenience, let us describe the algorithm
only for $A = \{a, b\}$. The hy\-poth\-eses imply that $\\deg(Q↓1U)
=\\deg(Q↓2V) ≥ 0$, $\\deg(Q↓1) ≤\\deg(Q↓2)$. If $\\deg(Q↓1)
= 0$, then $Q↓1$ is just a nonzero rational number, so we set
$Q = Q↓2/Q↓1$. Otherwise we let $Q↓1 = aQ↓{11} + bQ↓{12} + r↓1$,
$Q↓2 = aQ↓{21} + bQ↓{22} + r↓2$, where $r↓1$ and $r↓2$ are rational
numbers; it follows that
$$Q↓1U - Q↓2V = a(Q↓{11}U - Q↓{21}V) + b(Q↓{12}U - Q↓{22}V)
+ r↓1U - r↓2V.$$
We must have either $\\deg(Q↓{11}) =\\deg(Q↓1) -
1$ or $\\deg(Q↓{12}) =\\deg(Q↓1) - 1$. In the former case, $\\deg(Q↓{11}U
- Q↓{21}V) <\\deg(Q↓{11}U)$, by considering the terms of highest
degree that start with $a$; so we may replace 
$Q↓1$ by $Q↓{11}$, $Q↓2$ by $Q↓{21}$, and repeat the process. Similarly in
the latter case, we may replace $(Q↓1, Q↓2)$
by $(Q↓{12}, Q↓{22})$ and repeat the process.

(b)\9 We may assume that $\\deg(U) ≥\\deg(V)$. If
$\\deg(R) ≥\\deg(V)$, note that $Q↓1U - Q↓2V = Q↓1R - {(Q↓2 -
Q↓1Q)}V$ has degree less than $\\deg(V) ≤\\deg(Q↓1R)$, so we can
repeat the process with $U$ replaced by $R$; we obtain $R =
Q↑\prime V + R↑\prime$, $U = (Q + Q↑\prime )V + R↑\prime $, where
$\\deg(R↑\prime ) <\\deg(R)$, so eventually a solution will be
obtained.

(c)\9 The algorithm of (b) gives $V↓1 = UV↓2 + R$,
$\\deg(R) <\\deg(V↓2)$; by homogeneity, $R = 0$ and $U$ is homogeneous.

(d)\9 We may assume that $\\deg(V) ≤\\deg(U)$. If
$\\deg(V) = 0$, set $W ← U$; otherwise use (c) to find $U = QV$,
so that $QVV = VQV$, $(QV - VQ)V = 0$. This implies that $QV =
VQ$, so we can set $U ← V$, $V ← Q$ and repeat the process.

For further details about the subject of this
exercise, see P. M. Cohn, {\sl Proc.\ Cambridge Phil.\ Soc.\ \bf 57}
(1961), 18--30. The considerably more difficult problem of characterizing
{\sl all} string polynomials such that $UV = VU$ has been solved
by G. M. \α{Bergman} [Ph.D. thesis, Harvard University, 1967].

\ansno 18. [P. M. \α{Cohn,} {\sl Transactions Amer.\ Math.\ Soc.\ \bf 109}
(1963), 332--356.]

\yskip\hang\textindent{\bf C1.} Set $u↓1 ← U↓1$, $u↓2
← U↓2$, $v↓1 ← V↓1$, $v↓2 ← V↓2$, $z↓1 ← z↑\prime↓{2} ← w↓1 ← w↑\prime↓{2}
← 1$, $z↑\prime↓{1} ← z↓2 ← w↑\prime↓{1} ← w↓2 ← 0$, $n
← 0$.

\yskip\hang\textindent{\bf C2.} (At this point the identities
given in the exercise hold, and $u↓1v↓1 = u↓1v↓2$; $v↓2 =
0$ if and only if $u↓1 = 0$.)\xskip If $v↓2 = 0$, the algorithm terminates
with gcrd$(V↓1, V↓2) = v↓1$, lclm$(V↓1, V↓2) = z↑\prime↓{1}V↓1
= -z↑\prime↓{2}V↓2$.\xskip (Also, by symmetry, we have gcld$(U↓1, U↓2) = u↓2$ and
lcrm$(U↓1, U↓2) = U↓1w↓1 = -U↓2w↓2$.)

\yskip\hang\textindent{\bf C3.} Find $Q$ and $R$ such that $v↓1
= Qv↓2 + R$, where $\\deg(R) <\\deg(v↓2)$.\xskip$\biglp$We have $u↓1(Qv↓2
+ R) = u↓2v↓2$, so $u↓1R = (u↓2 - u↓1Q)v↓2 = R↑\prime v↓2.\bigrp$

\yskip\hang\textindent{\bf C4.} Set $(w↓1$, $w↓2$, $w↑\prime↓{1}$,
$w↑\prime↓{2}$, $z↓1$, $z↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$,
$u↓1$, $u↓2$, $v↓1$, $v↓2) ← (w↑\prime↓{1} - w↓1Q$, $w↑\prime↓{2}
- w↓2Q$, $w↓1$, $w↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$, $z↓1 - Qz↑\prime↓{1}$,
$z↓2 - Qz↑\prime↓{2}$, $u↓2 - u↓1Q$, $u↓1$, $v↓2$, $v↓1 - Qv↓2)$ and
$n ← n + 1$. Go back to C2.\quad\blackslug
%folio 802 galley 1a (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hbox{#1}}(}\def\+#1\biglp{\mathop{\hbox{#1}}\biglp}
\yyskip This extension of Euclid's algorithm includes most
of the features we have seen in previous extensions, all at
the same time, so it provides new insight into the special cases
already considered. To prove that it is valid, note first that
deg$(v↓2)$ decreases in step C4, so the algorithm certainly
terminates. At the conclusion of the algorithm, $v↓1$ is a common
right divisor of $V↓1$ and $V↓2$, since $w↓1v↓1 = (-1)↑nV↓1$
and $-w↓2v↓1 = (-1)↑nV↓2$; also if $d$ is any common right divisor
of $V↓1$ and $V↓2$, it is a right divisor of $z↓1V↓1 + z↓2V↓2
= v↓1$. Hence $v↓1 =\\gcrd(V↓1, V↓2)$. Also if $m$ is any common
left multiple of $V↓1$ and $V↓2$, we may assume without loss
of generality that $m = U↓1V↓1 = U↓2V↓2$, since the sequence
of values of $Q$ does not depend on $U↓1$ and $U↓2$. Hence $m
= (-1)↑n(-u↓2z↑\prime↓{1})V↓1 = (-1)↑n(u↓2z↑\prime↓{2})V↓2$
is a multiple of $z↑\prime↓{1}V↓1$.

In practice, if we just want to calculate gcrd$(V↓1,
V↓2)$, we may suppress the computation of $n$, $w↓1$, $w↓2$, $w↑\prime↓{1}$,
$w↑\prime↓{2}$, $z↓1$, $z↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$.
These additional quantities were added to the algorithm primarily
to make its validity more readily established.

{\sl Note:} Nontrivial factorizations of string
polynomials, such as the example given with this exercise, can
be found from matrix identities such as
\def\choptop#1{\vbox to 0pt{\vss\hbox{$#1$}}}
$$\left({a \atop 1}\hskip 1.5em{1\atop 0}\right)\left({\choptop b\atop 1}\hskip 1.5em{1\atop
0}\right)\left({c\atop 1}\hskip 1.5em{1\atop0}\right)\left({0\atop 1}\9
{\quad1\atop -c}\right)\left({0\atop 1}\9{\quad1\atop -b}\right)\left({0\atop
1}\9{\quad1\atop -a}\right) = \left({1\hskip 1.5em 0\atop 0\hskip 1.5em 1}\right),$$
since these identities hold even when multiplication is not commutative.
For example,
$$(abc + a + c)(1 + ba) = (ab + 1)(cba + a + c).$$
(Compare this with the ``\α{continuant polynomials}'' of Section 4.5.3.)

\ansno 19. [Cf.\ Eug\`ene \α{Cahen,} {\sl Th\'eorie des Nombres \bf1} (Paris: A.
Hermann & fils, 1914), \hbox{336--338}.]\xskip
If such an algorithm
exists, $D$ is a gcrd by the argument in exercise↔18. Let us
regard $A$ and $B$ as a single $2n \times n$ matrix $C$ whose
first $n$ rows are those of $A$, and whose second $n$ rows are
those of $B$. Similarly, $P$ and $Q$ can be combined into a
$2n \times n$ matrix $R$; $X$ and $Y$ can be combined into an
$n \times 2n$ matrix $Z$. The desired conditions now reduce
to two equations $C = RD$, $D = ZC$. If we can find a $2n \times
2n$ integer matrix $U$ with determinant $\pm 1$ such that the last
$n$ rows of $U↑{-1}C$ are all zero, then $R = ($first $n$ columns
of $U)$, $D = ($first $n$ rows of $U↑{-1}C)$, $Z = ($first $n$ rows
of↔$U↑{-1})$ solves the desired conditions. Hence, for example,
the following algorithm may be used (with $m=2n$):

\algbegin Algorithm T (\α{Triangulation}). Let $C$ be an $m \times n$ matrix
\inx{matrix triangulation}
of integers. This algorithm finds $m \times m$ integer matrices
$U$ and $V$ such that $UV = I$ and $VC$ is ``upper triangular.''\xskip
(The entry in row $i$ and column $j$ of $VC$ is zero if $i >
j$.)

\algstep T1. [Initialize.] Set $U ← V ← I$, the
$m \times m$ identity matrix; and set $T ← C$.\xskip (Throughout the
algorithm we will have $T = VC$ and $UV = 1$.)

\algstep T2. [Iterate on $j$.] Do step T3 for $j = 1$, 2, $\ldotss
$, $\min(m, n)$, and terminate the algorithm.

\algstep T3. [Zero out column $j$.] Perform the following transformation
zero or more times until $T↓{ij}$ is zero for all $i > j$: Let
$T↓{kj}$ be a nonzero element of $\{T↓{ij}, T↓{(j+1)j}, \ldotss,
T↓{mj}\}$ having the smallest absolute value. Interchange
rows $k$ and $j$ of $T$ and of $V$; interchange columns $k$
and $j$ of $U$. Then subtract $\lfloor T↓{ij}/T↓{jj}\rfloor$
times row $j$ from row $i$, in matrices $T$ and $V$, and add
the same multiple of column $i$ to column $j$ in matrix $U$,
for $j < i ≤ m$.\quad\blackslug

\yyskip\noindent For the stated example, the
algorithm yields \def\\#1#2#3#4{({#1\atop#3}\>{#2\atop#4})}
$\\1234=\\1032\\1{\quad2}0{-1}$, $\\4321=\\4523\\1{\quad2}0{-1}$,
$\\1{\quad2}0{-1}=\\1{\quad0}2{-2}\\1234
+\\0010\\4321$.\xskip (Actually
{\sl any} matrix with determinant $\pm 1$ would be a gcrd in this particular case.)

\ansno 20. It may be helpful to consider the construction of exercise 4.6.2--22,
with $p↑m$ replaced by a small number $ε$.

\ansno 21. Note that Algorithm R is used only when $m - n ≤
1$; furthermore, the coefficients are bounded by (25) with $m =
n$.\xskip [The stated formula is, in fact, the execution time observed
in practice, not merely an upper bound. For more detailed information
see G. E. \α{Collins,} {\sl Proc. 1968 Summer Inst.\ on Symbolic
Math.\ Comp.}, Robert G. \α{Tobey,} ed.\ (IBM Federal Systems Center:
June 1969), 195--231.]

\ansno 22. A sequence of signs cannot contain two consecutive
zeros, since $u↓{k+1}(x)$ is a nonzero constant in (29). Moreover
we cannot have ``+, 0, +'' or ``$-$, 0, $-$'' as subsequences. The formula
$V(u, a) - V(u, b)$ is clearly valid when $b = a$, so we must
only verify it as $b$ increases. The polynomials $u↓j(x)$ have
finitely many roots, and $V(u, b)$ changes only when $b$ encounters
or passes such roots. Let $x$ be a root of some (possibly several)
$u↓j$. When $b$ increases from $x - ε$ to $x$, the sign sequence
near $j$ goes from ``+, $\pm$, $-$'' to ``+, 0, $-$'' or from ``$-$, $\pm$, +''
to ``$-$, 0, +'' if $j > 0$; and from ``+, $-$'' to ``0, $-$'' or from ``$-$, +'' to
``0, +'' if $j = 0$.\xskip (Since $u↑\prime (x)$ is the derivative, $u↑\prime
(x)$ is negative when $u(x)$ is decreasing.)\xskip Thus the net change
in $V$ is $-\delta ↓{j0}$. When $b$ increases from $x$ to $x
+ ε$, a similar argument shows that $V$ remains unchanged.

[L. E. \α{Heindel,} {\sl JACM} {\bf 18} (1971), 533--548,
has applied these ideas to construct algorithms for isolating
the real zeros of a given polynomial $u(x)$, in time bounded
by a polynomial in deg$(u)$ and log $N$, where all coefficients
$y↓j$ are integers with $|u↓j| ≤ N$, and all operations are
guaranteed to be exact.]

\ansno 23. If $v$ has $n - 1$ real roots occurring between the
$n$ real roots of $u$, then (by considering sign changes) $u(x)\mod
v(x)$ has $n - 2$ real roots lying between the $n - 1$ roots of $v$.

\ansno 24. First show that $h↓j=g↓{\!j}↑{\delta↓{j-1}}g↓{\!j-1}↑{\delta↓{j-2}
(1-\delta↓{j-1})}\ldotss g↓2↑{\delta↓1(1-\delta↓2)\ldotsm(1-\delta↓{j-1})}$.
Then show that the exponent of $g↓2$ on the left-hand side of (18) has the form
$\delta↓2+\delta↓1x$, where $x=\delta↓2+\cdots+\delta↓{j-1}+1-\delta↓2(\delta↓3+
\cdots+\delta↓{j-1}+1)-\delta↓3(1-\delta↓2)(\delta↓4+\cdots+\delta↓{j-1}+1)-\cdots
-{\delta↓{j-1}(1-\delta↓2)\ldotsm(1-\delta↓{j-2})(1)}$. But $x=1$, since
it is seen to be independent of $\delta↓{j-1}$ and we can set $\delta↓{j-1}=0$,
etc. A similar derivation works for $g↓3$, $g↓4$, $\ldotss$, and a simpler
derivation works for (23).

\ansno 25. Each coefficient of $u↓j(x)$ can be expressed as a determinant in
which one column contains only $\lscr(u)$, $\lscr(v)$, and zeros. To use
this fact, modify Algorithm↔C as follows: In step C1, set $g←\gcd\biglp\lscr(u),
\lscr(v)\bigrp$ and $h←0$.
In step C3, if $h=0$, set $u(x)←v(x)$, $v(x)←r(x)/g$, $h←\lscr(u)↑\delta/g$,
$g←\lscr(u)$, and return to C2; otherwise proceed as in the unmodified
algorithm. The effect of this new initialization is simply to replace
$u↓j(x)$ by $u↓j(x)/\!\gcd\biglp\lscr(u),\lscr(v)\bigrp$ for all $j≥3$;
thus, $\lscr↑{2j-4}$ will become $\lscr↑{2j-5}$ in (28).

\def\dg{\mathop{\char d\char e\char g}}
\ansno 26. In fact, even more is true. Note that the algorithm in exercise↔3
computes $\pm p↓n(x)$ and $\mp q↓n(x)$ for $n≥-1$. Let $e↓n=\dg
(q↓n)$ and $d↓n=\dg(p↓nu-q↓nv)$; we observed in exercise↔3 that $d↓{n-1}+
e↓n=\dg(u)$ for $n≥0$. We shall prove that the conditions $\dg(q)<e↓n$ and
$\dg(pu-qv)<d↓{n-2}$ imply that $p(x)=c(x)p↓{n-1}(x)$ and $q(x)=c(x)q↓{n-1}(x)$:
Given such $p$ and $q$, we can find $c(x)$ and $d(x)$ such that $p(x)=c(x)p↓{n-1}(x)
+d(x)p↓n(x)$ and $q(x)=c(x)q↓{n-1}(x)+d(x)q↓n(x)$, since $p↓{n-1}(x)q↓n(x)-
p↓n(x)q↓{n-1}(x)=\pm1$. Hence $pu-qv=c(p↓{n-1}u-q↓{n-1}v)+d(p↓nu-q↓nv)$. If
${d(x)≠0}$, we must have $\dg(c)+e↓{n-1}=\dg(d)+e↓n$, since $\dg(q)<\dg(q↓n)$;
it follows that $\dg(c)+d↓{n-1}>\dg(d)+d↓n$, since this is surely true if $d↓n=
-∞$ and otherwise we have $d↓{n-1}+e↓n=d↓n+e↓{n+1}>d↓n+e↓{n-1}$. Therefore
$\dg(pu-qv)=\dg(c)+d↓{n-1}$; but we have assumed that $\dg(pu-qv)<d↓{n-2}=
d↓{n-1}+e↓n-e↓{n-1}$, so $\dg(c)<e↓n-e↓{n-1}$ and $\dg(d)<0$, a contradiction.

[This result is essentially due to L. \α{Kronecker},
{\sl Monatsberichte K\"onigl.\ Preu\ss.\ Akad.\ Wiss.\ }(Berlin: 1881),
535--600.
It implies the following theorem: ``Let $u(x)$ and↔$v(x)$ be relatively prime
polynomials over a field and let $d≤\dg(v)<\dg(u)$. If $q(x)$ is a polynomial
of least degree such that there exist polynomials $p(x)$ and↔$r(x)$ with
$p(x)u(x)-q(x)v(x)=r(x)$ and $\dg(r)=d$, then $p(x)/q(x)=p↓n(x)/q↓n(x)$ for
some↔$n$.'' For if $d↓{n-2}>d≥d↓{n-1}$, there are solutions $q(x)$
with $\dg(q)={e↓{n-1}+d-d↓{n-1}<e↓n}$, and we have proved that all solutions
of such low degree have the stated property.]
%folio 804 galley 1b (C) Addison-Wesley 1978	*
\ansbegin{4.6.2}

\ansno 1. By the principle of \α{inclusion
and exclusion} (Section 1.3.3), the number of polynomials without
linear factors is $\sum ↓{k≤n} {p\choose k}p↑{n-k}(-1)↑k = p↑{n-p}(p
- 1)↑p$. The stated probability when $n≥p$ is therefore $1 - (1 - 1/p)↑p$,
which is greater than ${1\over 2}$.\xskip [In fact, the stated probability
is greater than ${1\over 2}$ for all $n ≥ 1$.]\xskip The average number of
linear factors is $p$ times the average number of times $x$ is a factor,
so it is ${p\over p-1}(1-p↑{-n})=1+p↑{-1}+\cdots+p↑{1-n}$.\xskip
[See answer 38 for further comments on the average number of linear factors.]

\ansno 2. (a)\9 We know that $u(x)$ has a representation
as a product of irreducible polynomials; and the leading coefficients
of these polynomials must be units, since they divide the leading
coefficient of $u(x)$. Therefore we may assume that $u(x)$ has
a representation as a product of monic irreducible polynomials
$p↓1(x)↑{e↓1}\ldotsm p↓r(x)↑{e↓r}$, where $p↓1(x)$,
$\ldotss$, $p↓r(x)$ are distinct. This representation is unique,
except for the order of the factors, so the conditions on $u(x)$,
$v(x)$, $w(x)$ are satisfied if and only if
$$v(x) = p↓1(x)↑{\lfloor e↓1/2\rfloor} \ldotss p↓r(x)↑{\lfloor e↓r/2\rfloor},
\qquad w(x) = p↓1(x)↑{e↓1\mod2} \ldotss p↓r(x)↑{e↓r\mod2}.$$

(b)\9 The generating function for the number
of monic polynomials of degree $n$ is $1 + pz + p↑2z↑2 + \cdots
= 1/(1 - pz)$. The generating function for the number of polynomials
of degree $n$ having the form $v(x)↑2$, where $v(x)$ is monic,
is $1 + pz↑2 + p↑2z↑4 + \cdots = 1/(1 - pz↑2)$. If the generating
function for the number of monic squarefree polynomials of degree
$n$ is $g(z)$, then by part (a)  we must have $1/(1 - pz) = g(z)/(1 - pz↑2)$.
Hence $g(z) = (1 - pz↑2)/(1 - pz) = 1 + pz + (p↑2 - p)z↑2 +
(p↑3 - p↑2)z↑3 + \cdotss$. The answer is $p↑n - p↑{n-1}$ for
$n ≥ 2$.\xskip [Curiously, this proves that $\gcd\biglp u(x), u↑\prime
(x)\bigrp = 1$ with probability $1 - 1/p$; it is the same as
the probability that $\gcd\biglp u(x), v(x)\bigrp = 1$ when $u(x)$
and $v(x)$ are {\sl independent}, by exercise 4.6.1--5.]

{\sl Note:} By a similar argument, every $u(x)$ has a unique representation
$v(x)w(x)↑r$, where $v(x)$ is not divisible by the $r$th power of any
irreducible; the number of such monic polynomials $v(x)$ is $p↑n-p↑{n-r+1}$
for $n≥r$.

\ansno 3. Let $u(x) = u↓1(x) \ldotsm u↓r(x)$. There is {\sl at
most} one such $v(x)$, by the argument of Theorem↔4.3.2C\null. There
is {\sl at least} one if, for each $j$, we can solve the system
with $w↓j(x) = 1$ and $w↓k(x) = 0$ for $k ≠ j$. A solution to
the latter is $v↓1(x)\prod↓{k≠j}u↓k(x)$, where $v↓1(x)$
and $v↓2(x)$ can be found satisfying
$$\textstyle v↓1(x)\prod↓{k≠j}u↓k(x)\,+\,v↓2(x)u↓j(x) = 1,\qquad
\hbox{deg}(v↓1) <\hbox{deg}(u↓j),$$
by the extension of Euclid's algorithm (exercise↔4.6.1--3).
%folio 805 galley 2 (C) Addison-Wesley 1978	*
\ansno 4. By unique factorization, we have
$(1 - pz)↑{-1} =\prod↓{n≥1} (1 - z↑n)↑{-a↓{np}}$;
after taking logarithms, this can be rewritten$$\textstyle\sum ↓{j≥1} G↓p(z↑j)/j
= \sum ↓{k,j≥1} a↓{kp}z↑{kj}/j = \ln\biglp 1/(1 - pz)\bigrp.$$
The stated identity now yields the answer $G↓p(z) = \sum ↓{m≥1}
\mu (m)m↑{-1}\ln\biglp 1/(1 - pz↑m)\bigrp $, from which we
obtain $a↓{np} = \sum ↓{d\rslash n} \mu (n/d)n↑{-1}p↑d$; thus $\lim↓{p→∞}
a↓{np}/p↑n = 1/n$. To prove the stated identity, note that
$$\textstyle\sum
↓{n,j≥1}\mu (n)g(z↑{nj})n↑{-t}j↑{-t} = \sum ↓{m≥1} g(z↑m)m↑{-t}
\sum ↓{n\rslash m} \mu (n) = g(z).$$

\ansno 5. Let $a↓{npr}$ be the number of monic
polynomials of degree $n$ modulo $p$ having exactly $r$ irreducible
factors. Then $\Gscr↓p(z, w) = \sum ↓{n,r≥0} a↓{npr}z↑nw↑r =
\exp\biglp\lower6pt\null
 \sum ↓{k≥1} G↓p(z↑k)w↑k/k\bigrp$, where $G↓p$ is the generating
function in exercise↔4; cf.\ Eq.\ 1.2.9--34.
We have $$\baselineskip15pt\eqalign{\textstyle\sum ↓{n≥0} A↓{np}z↑n
= d\Gscr↓p(z/p, w)/d↓{\null}w\,|↓{w=1}⊗=\textstyle
\biglp \sum ↓{k≥1}G↓p(z↑k/p↑k)\bigrp \exp\biglp\ln(1/(1
- z))\bigrp\cr⊗\textstyle=\biglp\sum↓{n≥1}\ln\biglp 1/(1-p↑{1-n}z↑n)\bigrp\varphi
(n)/n\bigrp/(1-z),\cr}$$ hence $A↓{np} = H↓n + 1/2p + O(p↑{-2})$ for
$n ≥ 2$. The average value of $2↑r$ is the coefficient of $z↑n$
in $\Gscr↓p(z/p, 2)$, namely $n + 1 + (n - 1)/p + O(p↑{-2})$.\xskip (The
variance is of order $n↑3$, however: set $w = 4$.)

\ansno 6. For $0 ≤ s < p$, $x - s$ is a factor of
$x↑p - x$ (modulo $p$) by Fermat's theorem. So $x↑p - x$ is
a multiple of $\lcm\biglp x - 0, x - 1, \ldotss , x - (p - 1)\bigrp=x↑{\underline p}
$.\xskip [{\sl Note:} Therefore the \α{Stirling numbers}
$p\comb[]k$ are multiples of $p$ except when $k = 1$, $k =
p$. Equation 1.2.6--41 shows that the same statement is valid
for Stirling numbers $p\comb\{\} k$ of the other kind.]

\ansno 7. The factors on the right are relatively
prime, and each is a divisor of $u(x)$, so their product divides
$u(x)$. On the other hand, $u(x)$ divides
$$\textstyle v(x)↑p - v(x) = \prod ↓{0≤s<p}
\biglp v(x) - s\bigrp ,$$
so it divides the right-hand side by exercise↔4.5.2--2.

\ansno 8. The vector (18) is the only output whose $k$th component is nonzero.

\ansno 9. For example, start with $x ← 1$ and $y ← 1$;
then repeatedly set $R[x] ← y$, ${x ←2x \mod 101}$, $y ← 51y
\mod 101$, one hundred times.

\ansno 10. The matrix $Q - I$ below has a null space generated
by the two vectors $v↑{[1]} =(1, 0, 0, 0, 0, 0, 0, 0)$, $v↑{[2]}
= (0, 1, 1, 0, 0, 1, 1, 1)$. The factorization is
$$(x↑6 + x↑5 + x↑4 + x + 1)(x↑2 + x + 1).$$

\vskip-4pt
\hbox to size{\qquad$\dispstyle{p=2\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hbox to 15pt{\hfill#}⊗\!
\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}⊗\!
\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗1⊗1⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗1⊗0⊗1⊗0⊗0⊗0\cr
0⊗0⊗0⊗1⊗0⊗0⊗1⊗0\cr
1⊗0⊗0⊗1⊗0⊗0⊗1⊗0\cr
1⊗0⊗1⊗1⊗1⊗0⊗0⊗0\cr
0⊗0⊗1⊗0⊗1⊗1⊗0⊗1\cr
1⊗1⊗0⊗1⊗1⊗1⊗0⊗1\cr}}\,\right)}\hfill{p=5\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hbox to 15pt{\hfill#}⊗\!
\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}⊗\!
\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}⊗\hbox to 15pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗4⊗0⊗0⊗0⊗1⊗0\cr
0⊗2⊗2⊗0⊗4⊗3⊗4\cr
0⊗1⊗4⊗4⊗4⊗2⊗1\cr
2⊗2⊗2⊗3⊗4⊗3⊗2\cr
0⊗0⊗4⊗0⊗1⊗3⊗2\cr
3⊗0⊗2⊗1⊗4⊗2⊗1\cr}}\,\right)}$\qquad}

\ansno 11. Removing the trivial factor % WATCH PAGING HERE IN FUTURE EDITIONS
$x$, the matrix $Q - I$ on the previous page has a null space generated by
$(1, 0, 0, 0, 0, 0, 0)$ and $(0, 3, 1, 4, 1, 2, 1)$. The factorization
is
$$x(x↑2 + 3x + 4)(x↑5 + 2x↑4 + x↑3 + 4x↑2 + x + 3).$$

\ansno 12. If $p = 2$, $(x + 1)↑4 = x↑4 + 1$. If $p
= 8k + 1$, $Q - I$ is the zero matrix, so there are four factors.
For other values of $p$ we have
$$\lower18pt\hbox{$Q-I=\null$}
{p=8k+3\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hbox to 20pt{\hfill$#$}⊗\!
\hbox to 20pt{\hfill$#$}⊗\hbox to 20pt{\hfill$#$}⊗\hbox to 20pt{\hfill$#$}\cr
0⊗0⊗0⊗0\cr0⊗-1⊗0⊗1\cr0⊗0⊗-2⊗0\cr0⊗1⊗0⊗-1\cr}}\,\right)}
{p=8k+5\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hbox to 20pt{\hfill$#$}⊗\!
\hbox to 20pt{\hfill$#$}⊗\hbox to 20pt{\hfill$#$}⊗\hbox to 20pt{\hfill$#$}\cr
0⊗0⊗0⊗0\cr0⊗-2⊗0⊗0\cr0⊗0⊗0⊗0\cr0⊗0⊗0⊗-2\cr}}\,\right)}
{p=8k+7\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hbox to 20pt{\hfill$#$}⊗\!
\hbox to 20pt{\hfill$#$}⊗\hbox to 20pt{\hfill$#$}⊗\hbox to 20pt{\hfill$#$}\cr
0⊗0⊗0⊗0\cr0⊗-1⊗0⊗-1\cr0⊗0⊗-2⊗0\cr0⊗-1⊗0⊗-1\cr}}\,\right)}$$
Here $Q - I$ has rank 2, so there are $4
- 2 = 2$ factors.\xskip [But it is easy to prove that $x↑4 + 1$ is
irreducible over the integers, since it has no linear factors
and the coefficient of $x$ in any factor of degree two must
be less than or equal to 2 in absolute value by exercise↔20.
For all $k ≥ 2$, H. P. F. \α{Swinnerton-Dyer} has exhibited polynomials
of degree $2↑k$ that are irreducible over the integers, but
they split completely into linear and quadratic factors modulo
every prime. For degree 8, his example is $x↑8 - 16x↑6 + 88x↑4
+192x↑2 + 144$, having roots $\pm\sqrt 2\pm\sqrt3\pm i$ [see {\sl Math.\
Comp.\ \bf24} (1970), 733--734]. According to the theorem of \α{Frobenius} cited
in exercise↔37, any irreducible polynomial of degree $n$
whose \α{Galois group} contains no $n$-cycles will have factors modulo almost
all primes.]

\ansno 13. $p=8k+1$:
${\biglp x+(1+\sqrt{-1})/\sqrt2\bigrp}\*
{\biglp x+(1-\sqrt{-1})/\sqrt2\bigrp}\*
{\biglp x-(1+\sqrt{-1})/\sqrt2\bigrp}\*
{\biglp x-(1-\sqrt{-1})/\sqrt2\bigrp}$.\xskip
$p=8k+3$: ${\biglp x↑2-\sqrt{-2}x-1\bigrp}\*
{\biglp x↑2-\sqrt{-2}x-1\bigrp}$.\xskip
$p=8k+5$: ${\biglp x↑2-\sqrt{-1}\bigrp}\*
{\biglp x↑2-\sqrt{-1}\bigrp}$.\xskip
$p=8k+7$: ${\biglp x↑2-\sqrt2x+1\bigrp}\*
{\biglp x↑2+\sqrt2x+1\bigrp}$. The latter factorization also holds over the
field of real numbers.

\ansno 14. Algorithm N can be adapted to find the coefficients
\inx{null space}
of $w$: Let $A$ be the $(r + 1) \times n$ matrix whose $k$th
row contains the coefficients of $v(x)↑k \mod
u(x)$, for $0 ≤ k ≤ r$. Apply the method of Algorithm↔N until
the first dependence is found in step N3; then the algorithm
terminates with $w(x) = v↓0 + v↓1x +\cdots + v↓kx↑k$,
where $v↓j$ is defined in (18).
At this point $2 ≤ k ≤ r$; it is not necessary to know $r$ in advance, since
we can check for dependency after generating each row of $A$.


\ansno 15. We may assume that $u≠0$ and that $p$ is odd. \α{Berlekamp}'s method applied
to the polynomial $x↑2-u$ tells us that a square root exists if and only if
$u↑{(p-1)/2}\mod p=1$; let us assume that this condition holds.

Let $p-1=2↑e\cdot q$, where $q$ is odd. \α{Zassenhaus}'s factoring procedure suggests
the following square-root extraction algorithm: Set $t←0$. Evaluate
$$\twoline{\gcd\biglp(x+t)↑q-1,x↑2-u\bigrp,\;\gcd\biglp(x+t)↑{2q}-1,x↑2
-u\bigrp,}{2pt}{\gcd\biglp(x+t)↑{4q}-1,x↑2-u\bigrp,\;\gcd\biglp(x+t)↑{8q}-1,
x↑2-u\bigrp,\;\ldotss,}$$
until finding the first case where the gcd is not 1 (modulo $p$). If the
gcd is $x-v$, then $\sqrt u = \pm v$. If the gcd is $x↑2-u$, set $t←t+1$ and
repeat the calculation.

{\sl Notes:} If $(x+t)↑k\mod(x↑2-u)=ax+b$, then we have $(x+t)↑{k+1}\mod(x↑2-u)=
(b+at)x+(bt+au)$, and $(x+t)↑{2k}\mod(x↑2-u)=2abx+(b↑2+a↑2u)$; hence
$(x+t)↑q$, $(x+t)↑{2q}$, $\ldots$ are easy to evaluate efficiently, and the
calculation for fixed $t$ takes $O\biglp(\log p)↑3\bigrp$ units of time.
The square root will be found when $t=0$ with probability $1/2↑{e-1}$;
thus it will always be found immediately when $p\mod4=3$. If we choose
$t$ at random instead of increasing it sequentially, exercise↔29 gives a
rigorous proof that each↔$t$ gives success at least about half of the time;
but for practical purposes this random choice isn't needed.

Another square-root method has been suggested by D. \α{Shanks}. When $e>1$ it
requires an auxiliary constant $z$ (depending only on $p$) such that
$z↑{2↑{e-1}}≡-1\modulo p$. The value $z=n↑q\mod p$ will work for almost
one half of all integers $n$; once $z$ is known, the following algorithm
requires no more probabilistic calculation:

\yskip\hang\textindent{\bf S1.}Set $y←z$, $r←e$, $v←u↑{(q+1)/2}\mod p$,
$w←u↑q\mod p$.

\yskip\hang\textindent{\bf S2.}If $w=1$, stop; $v$ is the answer. Otherwise
find the smallest $k$ such that $w↑{2↑k}\mod p$ is equal to 1.
If $k=r$, stop (there is
no answer); otherwise set$$(y,r,v,w)←(y↑{2↑{r-k}},k,vy↑{2↑{r-k-1}},wy↑{2↑{r-k}})$$
and repeat step S2.\quad\blackslug

\yyskip The validity of this algorithm follows from the invariant congruences
$uw≡v↑2$, $y↑{2↑{r-1}}≡-1$, $w↑{2↑{r-1}}≡1\modulo p$. On the average, step S2
will require about ${1\over4}e↑2$ multiplications mod $p$.\xskip
Reference: {\sl Proc.\ Second Manitoba Conf.\ Numer.\ Math.\ }(1972),
\hbox{58--62.} A related method was published by A. \α{Tonelli,} {\sl G\"ottinger
Nachrichten} (1891), 344--346.
%folio 810 galley 3 (C) Addison-Wesley 1978	*
\ansno 16. (a)\9 Substitute polynomials modulo $p$ for integers,
in the proof for $n = 1$.\xskip (b) The proof for $n=1$
carries over to any finite field.\xskip (c) Since $x = \xi ↑k$ for
some $k$, $x↑{p↑{\vbox to 3pt{}n}} = x$ in the field defined by $f(x)$.
Furthermore, the elements $y$ that satisfy the equation $y↑{p↑m} = y$ in the field
are closed under addition, and closed under multiplication;
so if $x↑{p↑m}= x$, then $\xi$ (being a polynomial in
$x$ with integer coefficients) satisfies $\xi↑{p↑m} =
\xi $.

\ansno 17. If $\xi$ is a primitive root, each nonzero element
is some power of $\xi $. Hence the order must be a divisor of
$13↑2 - 1 = 2↑3 \cdot 3 \cdot 7$, and $\varphi (f)$ elements have
order $f$.
\def\\#1{\hbox{$\hfill\hskip-10pt#1\hskip-10pt\hfill$}\hfill}
$$\vbox{\halign{\hfill#⊗\qquad\hfill#⊗\qquad\qquad\hfill#⊗\qquad\hfill#⊗\!
\qquad\qquad\hfill#⊗\qquad\hfill#⊗\qquad\qquad\hfill#⊗\qquad\hfill#\cr
\\f⊗\\{\varphi(f)}⊗\\f⊗\\{\varphi(f)}⊗\\f⊗\\{\varphi(f)}⊗\\f⊗\\{\varphi(f)}\cr
\noalign{\vskip3pt}
1⊗1⊗3⊗2⊗7⊗6⊗21⊗12\cr
2⊗1⊗6⊗2⊗14⊗6⊗42⊗12\cr
4⊗2⊗12⊗4⊗28⊗12⊗84⊗24\cr
8⊗4⊗24⊗8⊗56⊗24⊗168⊗48\cr}}$$

\ansno 18. (a)\9 pp$\biglp p↓1(u↓nx)\bigrp \ldotsm\hbox{pp}
\biglp p↓r(u↓nx)\bigrp$, by \α{Gauss's lemma}. For example, let
$$u(x) = 6x↑3 - 3x↑2 + 2x - 1,\qquad v(x) = x↑3 - 3x↑2 + 12x
- 36 = (x↑2 + 12)(x - 3);$$
then pp$(36x↑2 + 12) = 3x↑2 + 1$, pp$(6x - 3) =
2x - 1$.\xskip (This is a modern version of a fourteenth-century trick
used for many years to help solve algebraic equations.)

(b)\9 Let pp$\biglp w(u↓nx)\bigrp = \=w↓mx↑m
+ \cdots + \=w↓0 = w(u↓nx)/c$, where $c$ is the content
of $w(u↓nx)$ as a polynomial in $x$. Then $w(x) = (c\=w/u↑{m}↓{n})x↑m
+ \cdots + c\=w↓0$, hence $c\=w↓m = u↑{m}↓{n}$;
since $\=w↓m$ is a divisor of $u↓n$, $c$ is a multiple of $u↑{m-1}↓{n}$.

\ansno 19. If $u(x) = v(x)w(x)$ with deg$(v)$deg$(w) ≥
1$, then $u↓nx↑n ≡ v(x)w(x) \modulo p$. By unique factorization
modulo $p$, all but the leading coefficients of $v$ and $w$ are multiples of $p$,
and $p↑2$ divides $v↓0w↓0=u↓0$.

\ansno 20. (a)\9 $\sum (αu↓j - u↓{j-1})(\=α
{\=u}↓j - {\=u}↓{j-1}) = \sum (u↓j - \=αu↓{j-1})({\=u}↓j
- α{\=u}↓{j-1})$.\xskip (b) We may assume that $u↓0 ≠ 0$. Let
$m(u) = \prod↓{1≤j≤n} \min(1, |α↓j|) = u↓0/M(u)u↓n$. Whenever
$|α↓j| < 1$, change the factor $x - α↓j$ to ${\=α}↓jx -
1$ in $u(x)$; this doesn't affect $|u|$. Now looking at the
leading and trailing coefficients only, we have $|u|↑2 ≥ |u↓n|↑2m(u)↑2
+ |u↓n|↑2M(u)↑2$; hence we obtain the slightly stronger result
$M(u)↑2 ≤ \biglp |u|↑2 + (|u|↑4 - 4|u↓0u↓n|↑2)↑{1/2}\bigrp
/2|u↓n|↑2$.\xskip
[A further improvement in the estimate of $M(u)$ can often be obtained by
replacing $u(x)$ by the polynomial $\A u(x)=\biglp x↑k-s↓k/|u|↑2\bigrp u(x)$,
where $s↓k=\sum↓j\=u↓ju↓{j-k}$; since $M(\A u)=M(u)$ and $|\A u|↑2=|u|↑2-
|s↓k|↑2\!/|u|↑2$, we obtain the inequality $|u|↑2-|s↓k|↑2\!/|u|↑2≥|u↓0|↑2|s↓k|↑2
\!/\biglp|u|↑4M(u)↑2\bigrp+|u↓n|↑2M(u)↑2$ for $1≤k<n$. In the case of polynomial↔
(22), we have $s↓2=-72$ and we obtain the bound $M(u)<8.1837$.]\xskip
(c)↔$u↓j = u↓m \sum α↓{i↓1}\ldotsm α↓{i↓{m-j}}$,
an elementary symmetric function, hence
$|u↓j| ≤ |u↓m| \sum β↓{i↓1} \ldotsm β↓{i↓{m-j}}$
where $β↓i = \max(1, |α↓i|)$. We complete the proof by showing
that when $x↓1≥1$, $\ldotss$, $x↓n≥1$, and $x↓1 \ldotsm x↓n = M$,
the elementary symmetric function $\sigma ↓{nk} = \sum x↓{i↓1}
\ldotsm x↓{i↓k}$ is $≤{n-1\choose k-1}M + {n-1\choose k}$,
the value assumed when $x↓1 = \cdots = x↓{n-1} = 1$ and $x↓n
= M$.\xskip$\biglp$For if $x↓1 ≤ \cdots ≤ x↓n < M$, the transformation $x↓n
← x↓{n-1}x↓n$, $x↓{n-1} ← 1$ increases $\sigma ↓{nk}$ by $\sigma
↓{(n-2)(k-1)}(x↓n - 1)(x↓{n-1} - 1)$, which is positive.$\bigrp$\xskip
(d)↔$|v↓j| ≤ |v↓m|
\mathopen{\vcenter{\hbox{\:@\char'0}}}{m-1\choose j}M(v)+
{m-1\choose j-1}\mathclose{\vcenter{\hbox{\:@\char'1}}}≤|u↓n|
\mathopen{\vcenter{\hbox{\:@\char'0}}}{m-1\choose j}M(u)+
{m-1\choose j-1}\mathclose{\vcenter{\hbox{\:@\char'1}}}$
since $|v↓m| ≤ |u↓n|$ and
$M(v) ≤ M(u)$.\xskip [See
J. \α{Vicente Gon\c calves}, {\sl Revista de Faculdade de Ci\A encias} (2) A
{\bf1} (Univ. Lisbon, 1950), 167--171;
M. \α{Mignotte,} {\sl Math.\ Comp.\ \bf 28} (1974), 1153--1157;
Mignotte and \α{Payafar}, {\sl RAIRO Analyse num\'er.\ \bf13} (1979), 181--192.]

\ansno 21. (a)\9 $\int↑{1}↓{0}\biglp u↓ne(n\theta ) + \cdots + u↓0)({\=u}↓n
e(-n\theta ) + \cdots + {\=u}↓0)\,d\theta = |u↓n|↑2 +
\cdots + |u↓0|↑2$ since $\int ↑{1}↓{0} e(j\theta )e(-k\theta
)\,d\theta = \delta↓{jk}$; now use induction on $t$.\xskip (b) Since
$|v↓j| ≤ {m\choose j}M(v)|v↓m|$ we conclude that $|v|↑2 ≤ {2m\choose
m}M(v)↑2|v↓m|↑2$. Hence $|v|↑2|w|↑2 ≤ {2m\choose m}{2k\choose
k}M(v)↑2M(w)↑2|v↓mw↓k|↑2 = f(m, k)M(u)↑2|u↓n|↑2 ≤ f(m, k)|u|↑2$.\xskip
[Slightly better values for $f(m, k)$ are possible based on
the more detailed information in exercise↔20.]\xskip (c) The case
$t = 3$ suffices to show how to get from $t - 1$ to $t$. When
$t = 2$ we have shown that, for all $\theta ↓1$, $$\twoline{\textstyle\int ↑{1}↓{0}
\int ↑{1}↓{0} \int ↑{1}↓{0} \int ↑{1}↓{0}\left|v\biglp e(\theta
↓1), e(\phi ↓2), e(\phi ↓3)\bigrp\right|↑2\left|w\biglp e(\theta ↓1),
e(\psi ↓2), e(\psi ↓3)\bigrp \right|↑2\,d\phi ↓2\,d\phi ↓3\,d\psi ↓2\,
d\psi ↓3}{3pt}{\textstyle≤ f(m↓2, k↓2)f(m↓3, k↓3) \int ↑{1}↓{0} \int ↑{1}↓{0}
\left|v\biglp e(\theta ↓1), e(\theta ↓2), e(\theta ↓3)\bigrp \right|↑2
\left|w\biglp e(\theta ↓1), e(\theta ↓2), e(\theta ↓3)\bigrp \right|↑2
\,d\theta ↓2\,d\theta ↓3.}$$ For all $\phi ↓2$, $\phi ↓3$, $\psi ↓2$,
$\psi ↓3$ we have also shown that$$\twoline{\textstyle\int ↑{1}↓{0} \int ↑{1}↓{0}
\left|v\biglp e(\phi ↓1), e(\phi ↓2), e(\phi ↓3)\bigrp \right|↑2\left|w\biglp
e(\psi ↓1), e(\psi ↓2), e(\psi ↓3)\bigrp \right|↑2\,d\phi ↓1\,d\psi
↓1}{3pt}{\textstyle≤ f(m↓1, k↓1) \int ↑{1}↓{0}\left|v\biglp e(\theta ↓1), e(\phi
↓2), e(\phi ↓3)\bigrp \right|↑2\left|w\biglp e(\theta ↓1), e(\psi ↓2),
e(\psi ↓3)\bigrp \right|↑2\, d\theta ↓1.}$$Integrate the former inequality
with respect to $\theta ↓1$ and the latter with respect to $\phi
↓2$, $\phi ↓3$, $\psi ↓2$, $\psi ↓3$.\xskip [This method was used by A.
O. \α{Gel'fond} in {\sl Transcendental and Algebraic Numbers} (New
York: Dover, 1960), Section 3.4, to derive a slightly different
result.]

\def\\{\hbox{deg}}
\ansno 22. More generally, assume that $u(x) ≡ v(x)w(x)\modulo
q$, $a(x)v(x) + b(x)w(x) ≡ 1 \modulo p$, and $c\lscr(v) ≡ 1
\modulo r$, $\\(a) < \\(w)$, $\\(b) < \\(v)$, $\\(u)
= \\(v) + \\(w)$, where $r = \gcd(p, q)$ and $p, q$ needn't
be prime. We shall construct polynomials $V(x) ≡ v(x)$ and $W(x)
≡ w(x) \modulo q$ such that $u(x) ≡ V(x)W(x) \modulo {qr}$,
$\lscr(V) = \lscr(v)$, $\\(V) = \\(v)$, $\\(W) =\\(w)$; furthermore,
if $r$ is prime, the results will be unique modulo $qr$.

The problem asks us to find $\=v(x)$ and
$\=w(x)$ with $V(x) = v(x) + q\=v(x)$, $W(x)
= w(x) + q\=w(x)$, $\\(\=v) < \\(v)$, $\\(\=w)≤
\\(w)$; and the other condition$$\biglp v(x) + q\=v
(x)\bigrp\biglp w(x) + q\=w(x)\bigrp ≡ u(x)\;\modulo
{qr}$$is equivalent to $\=w(x)v(x) + \=v(x)w(x)
≡ f(x)\modulo r$, where $f(x)$ satisfies $u(x) ≡ v(x)w(x) + qf(x) \modulo
{qr}$. We have$$\biglp a(x)f(x) + t(x)w(x)\bigrp v(x) + \biglp
b(x)f(x) - t(x)v(x)\bigrp w(x) ≡ f(x)\;\modulo r$$for all
$t(x)$. Since $\lscr(v)$ has an inverse modulo $r$, we can find
a quotient $t(x)$ by Algorithm↔4.6.1D such that $\\(bf - tv)
< \\(v)$; for this $t(x)$, $\\(af + tw) ≤ \\(w)$, since we have
$\\(f) ≤ \\(u) = \\(v) + \\(w)$. Thus the desired
solution is $\=v(x) = b(x)f(x) - t(x)v(x) = b(x)f(x)\mod
v(x)$, $\=w(x) = a(x)f(x) + t(x)w(x)$. If $\biglp \={\=v}
(x), \={\=w}(x)\bigrp$ is another
solution, we have $\biglp \=w(x) - \={\=w}(x)\bigrp
v(x) ≡ \biglp \={\=v}(x) - \=v(x)\bigrp w(x)
\modulo r$. Thus if $r$ is prime, $v(x)$ must divide $\={\=v}
(x) - \=v(x)$; but $\\(\={\=v}
- \=v) < \\(v)$, so $\={\=v}(x) = 
\=v(x)$ and $\={\=w}(x) = \=w(x)$.

For $p = 2$, the factorization proceeds as follows
(writing only the coefficients, and using bars for negative
digits): Exercise↔10 says that $v↓1(x) = (\overline1\,\overline
1\,\overline1)$, $w↓1(x) = (\overline1\,\overline1\,\overline1\,
0\,0\,\overline1\,\overline1)$ in one-bit two's complement notation.
Euclid's extended algorithm yields $a(x) = (1\,0\,0\,0\,0\,1), b(x)
= (1\,0)$. The factor $v(x) = x↑2 + c↓1x + c↓0$ must have $|c↓1|
≤ \lfloor 1 + \sqrt{113}\rfloor = 11$, $|c↓0| ≤ 10$, by exercise↔20.
Three applications of Hensel's lemma yield $v↓4(x) = (1\,
3\,\overline1)$, $w↓4(x) = (1\,\overline3\,\overline5\,\overline4\,
4\,\overline3\,5)$. Thus $c↓1 ≡ 3$ and $c↓0 ≡ -1\modulo {16}$;
the only possible quadratic factor of $u(x)$ is $x↑2 + 3x -
1$. Division fails, so $u(x)$ is irreducible.\xskip$\biglp$Since we have
now proved the irreducibility of this beloved polynomial by
four separate methods, it is unlikely that it has any factors.$\bigrp$

Hans \α{Zassenhaus} has observed that we can often
speed up such calculations by increasing $p$ as well as $q$:
In the above notation, we can find $A(x)$, $B(x)$ such that $A(x)V(x)
+ B(x)W(x) ≡ 1 \modulo {pr}$, namely by taking $A(x) = a(x)
+ p\=a(x)$, $B(x) = b(x) + p\=b(x)$, where $\=a
(x)V(x) + \=b(x)W(x) ≡ g(x)\modulo r$, $a(x)V(x)
+ b(x)W(x) ≡ 1 - pg(x) \modulo {pr}$. We can also find $C$
with $\lscr(V)C ≡ 1\modulo {pr}$. In this way we can lift a
squarefree factorization $u(x) ≡ v(x)w(x) \modulo p$ to its
unique extensions modulo $p↑2$, $p↑4$, $p↑8$, $p↑{16}$, etc. However,
this ``accelerated'' procedure reaches a point of diminishing
returns in practice, as soon as we get to double-precision moduli,
since the time for multiplying multiprecision numbers in practical
ranges outweighs the advantage of squaring the modulus directly.
From a computational standpoint it seems best to work with the
successive moduli $p$, $p↑2$, $p↑4$, $p↑8$, $\ldotss$, $p↑E$, $p↑{E+e}$,
$p↑{E+2e}$, $p↑{E+3e}$, $\ldotss $, where $E$ is the smallest power
of 2 with $p↑E$ greater than single precision and $e$ is the
largest integer such that $p↑e$ has single precision.

Hensel's lemma, which K. \α{Hensel} introduced in order to
demonstrate the factorization of polynomials over the field
of \α{$p$-adic numbers} (see exercise 4.1--31), can be generalized
in several ways. First, if there are more factors, say $u(x)
≡ v↓1(x)v↓2(x)v↓3(x) \modulo p$, we can find $a↓1(x)$, $a↓2(x)$,
$a↓3(x)$ such that $a↓1(x)v↓2(x)v↓3(x) + a↓2(x)v↓1(x)v↓3(x) +
a↓3(x)v↓1(x)v↓2(x) ≡ 1 \modulo p$ and $\\(a↓i) < \\(v↓i)$.\xskip
$\biglp$In essence, $1/u(x)$ is expanded in partial fractions as $\sum
a↓i(x)/v↓i(x)$.$\bigrp$\xskip An exactly analogous construction now allows
us to lift the factorization without changing the leading coefficients
of $v↓1$ and $v↓2$; we take $\=v↓1(x) = a↓1(x)f(x)\mod
v↓1(x)$, $\=v↓2(x) = a↓2(x)f(x)\mod v↓2(x)$, etc. Another
important generalization is to several simultaneous moduli,
of the respective forms $p↑e$, $(x↓2 - a↓2)↑{n↓2}$, $\ldotss
$, $(x↓t - a↓t)↑{n↓t}$, when performing multivariate gcds
and factorizations. Cf.\ D. Y. Y. \α{Yun,} Ph.D. Thesis (M.I.T.,
1974).

\ansno 23. The \α{discriminant} of pp$\biglp u(x)\bigrp$ is a nonzero integer (cf.\
exercise 4.6.1--12), and there are multiple factors modulo $p$
iff $p$ divides the discriminant.\xskip[The factorization of (22)
modulo 3 is $(x + 1)(x↑2 - x - 1)↑2(x↑3 + x↑2 - x + 1)$; squared
factors for this polynomial occur only for $p = 3$, 23, 233,
and 121702457. It is not difficult to prove that the smallest
prime that is not unlucky is at most $O(n\log Nn)$, if $n
= \\(u)$ and $N$ bounds the coefficients of $u(x)$.]

%folio 818 galley 4a (C) Addison-Wesley 1978	*
\ansno 24. Multiply a monic polynomial with rational coefficients
by a suitable nonzero integer, to get a primitive polynomial
over the integers. Factor this polynomial over the integers,
and then convert the factors back to monic.\xskip (No factorizations
are lost in this way; see exercise↔4.6.1--8.)

\ansno 25. Consideration of the constant term shows there are
no factors of degree 1, so if the polynomial is reducible, it
must have one factor of degree 2 and one of degree 3. Modulo
2 the factors are $x(x + 1)↑2(x↑2+x+1)$; this is not much help.
Modulo 3 the factors are $(x + 2)↑2(x↑3+2x+2)$. Modulo 5 they
are $(x↑2 + x + 1)(x↑3 + 4x + 2)$. So we see that the answer
is $(x↑2 + x + 1)(x↑3 - x + 2)$.

\ansno 26. Begin with $D ← (0 \ldotsm 0 1)$, representing the
set $\{0\}$. Then for $1 ≤ j ≤ r$, set $D ← D ∨ (D\lsh d↓j)$,
where $∨$ denotes \α{logical ``or''} and $D\lsh d$ denotes $D$ shifted left
$d$ bit positions.\xskip$\biglp$Actually we need only work with a bit
vector of length $\lceil(n + 1)/2\rceil$, since $n - m$ is in the set iff
$m$ is.$\bigrp$

\ansno 27. Exercise 4 says that a random polynomial of degree
$n$ is irreducible modulo $p$ with rather low probability, about
$1/n$. But the Chinese remainder theorem implies that a random
monic polynomial of degree $n$ over the integers will be reducible
with respect to each of $k$ distinct primes with probability
about $(1 - 1/n)↑k$, and this approaches zero as $k → ∞$. Hence
almost all polynomials over the integers are irreducible with
respect to infinitely many primes; and almost all primitive
polynomials over the integers are irreducible.\xskip [Another proof
has been given by W. S. \α{Brown,} {\sl AMM \bf 70} (1963), 965--969. See
also the generalization cited in the answer to exercise↔36.]

\def\\{\hbox{deg}}
\ansno 28. Cf.\ exercise↔4; the probability is the coefficient
of $z↑n$ in ${(1\!+\!a↓{1p}z/p)}\*
{(1\!+\!a↓{2p}z↑2\!/p↑2)}\*{(1\!+\!a↓{3p}z↑3/p↑3)}\ldotsm $, which has the
limiting value $g(z) = {(1 + z)}\*{(1 + {1\over 2}z↑2)}\*
{(1 + {1\over 3}z↑3)}\ldotsm\,$. For $1 ≤ n ≤ 10$ the answers are 1, ${1\over
2}$, ${5\over 6}$, ${7\over 12}$, ${37\over 60}$, ${79\over
120}$, ${173\over 280}$, ${101\over 168}$, ${127\over 210}$, ${1033\over
1680}$.\xskip{\:a[}Let
$f(y) = \ln(1 + y) - y = O(y↑2)$. We have $$\textstyle g(z) = \exp\biglp \sum
↓{n≥1} z↑n/n + \sum ↓{n≥1} f(z↑n/n)\bigrp =
h(z)/(1 - z),$$ and it can be shown that the limiting probability
is $h(1) =
\exp\biglp \sum ↓{n≥1} f(1/n)\bigrp =e↑{-\gamma}\approx .56146$
as $n → ∞$; cf.\ D. H. \α{Lehmer,} {\sl Acta Arith.\ \bf 21} (1972),
379--388. Indeed, N.↔G. \α{de Bruijn} has established the asymptotic
formula $\lim↓{p→∞} a↓{np} =
e↑{-\gamma}+ e↑{-\gamma}/n + O(n↑{-2}\log n)$.{\:a]}

\ansno 29. Let $q↓1(x)$ and $q↓2(x)$ be any two of the irreducible divisors of
$g(x)$. By the Chinese remainder theorem (exercise↔3), choosing a random polynomial
$t(x)$ of degree $<2d$ is equivalent to choosing two random polynomials
$t↓1(x)$ and $t↓2(x)$ of degrees $<d$, where $t↓i(x)=t(x)\mod q↓i(x)$. The gcd
will be a proper factor if $t↓1(x)↑{(p↑d-1)/2}\mod q↓1(x)=1$ and
$t↓2(x)↑{(p↑d-1)/2}\mod q↓1(x)≠1$, or vice versa, and this condition holds for
exactly $2\biglp(p↑d-1)/2\bigrp\biglp(p↑d+1)/2\bigrp=(p↑{2d}-1)/2$ choices of
$t↓1(x)$ and $t↓2(x)$.

{\sl Notes:} We are considering here only the behavior with respect to two
irreducible factors, but the true behavior is probably much better. Suppose that each
irreducible factor $q↓i(x)$ has probability $1\over2$ of dividing $t(x)↑{(p↑d-1)/2}-1$
for each $t(x)$, independent of the behavior for other $q↓j(x)$ and $t(x)$; and
assume that $g(x)$ has $r$ irreducible factors in all.
Then if we encode each $q↓i(x)$ by a sequence of 0's and 1's
according as $q↓i(x)$ does or doesn't divide $t(x)↑{(p↑d-1)/2}-1$ for the successive
$t$'s tried, we obtain a random binary \α{trie} with $r$ lieves (cf.\ Section 6.3).
The cost associated with an internal node of this trie, having $m$ lieves as
descendants, is $O\biglp m↑2(\log p)\bigrp$; and the solution to
the recurrence $A↓n={n\choose2}+2↑{1-n}\sum{n\choose k}A↓k$ is $A↓n=2{n\choose2}$,
by exercise 5.2.2--36. Hence the sum of costs
in the given random trie---representing the expected time to factor $g(x)$ {\sl
completely}---is $O\biglp r↑2(\log p)↑3\bigrp$ under this
plausible assumption. The plausible assumption becomes rigorously true if we choose
$t(x)$ at random of degree $<rd$ instead of restricting it to degree $<2d$.

\ansno 30. Let $T(x)=x+x↑p+\cdots+x↑{p↑{d-1}}$ and $v(x)=T\biglp t(x)\bigrp
\mod q(x)$. Since $t(x)↑{p↑d}=t(x)$ in the field of polynomial remainders
modulo $q(x)$, we have $v(x)↑p=v(x)$ in that field; in other words, $v(x)$
is one of the $p$ roots of the equation $y↑p-y=0$. Hence $v(x)$ is an integer.

It follows that $\prod↓{0≤s<p}\gcd\biglp g↓d(x),T\biglp t(x)\bigrp-s\bigrp=
g↓d(x)$. In particular, when $p=2$ we can argue as in exercise 29 that
$\gcd\biglp g↓d(x),T\biglp t(x)\bigrp\bigrp$ will be a proper factor of $g↓d(x)$
with probability $≥{1\over2}$ when $g↓d(x)$ has at least two irreducible
factors and $t(x)$ is a random binary polynomial of degree $<2d$.

[Note that $T\biglp t(x)\bigrp\mod g(x)$ can be computed by starting with
$u(x)←t(x)$ and setting $u(x)←\biglp u(x)+u(x)↑p\bigrp\mod g(x)$ repeatedly,
$d-1$ times. The method of this exercise is based on the polynomial
factorization $x↑{p↑d}-x=\prod↓{0≤s<p}\biglp T(x)-s\bigrp$, which holds for
any↔$p$, while formula
(21) is based on the polynomial factorization $x↑{p↑d}-x=x(x↑{(p↑d-1)/2}+1)
(x↑{(p↑d-1)/2}-1)$ for odd↔$p$.]

\ansno 31. If $α$ is an element of the field of $p↑d$ elements, let $d(α)$ be
the ``degree'' of $α$, namely the smallest exponent $e$ such that $α↑{p↑e}=α$.
Then$$P↓α(x)=(x-α)(x-α↑p)\ldotsm(x-α↑{p↑{d-1}})=q↓α(x)↑{d/d(α)},$$where
$q↓α(x)$ is an irreducible polynomial of degree $d(α)$. As $α$ runs through
all elements of the field, the corresponding
$q↓α(x)$ runs through every irreducible polynomial
of degree $e$ dividing↔$d$, where every such irreducible occurs exactly $e$
times. We have $(x+t)↑{(p↑d-1)/2}\mod q↓α(x)=1$ if and only if $(α+t)↑
{(p↑d-1)/2}=1$ in the field. If $t$ is an integer, we have $d(α+t)=d(α)$,
hence $n(p,d)$ is $d↑{-1}$ times the number of elements $α$ of degree $d$
such that $α↑{(p↑d-1)/2}=1$. Similarly, if $t↓1≠t↓2$ we want to count the
number of elements of degree $d$ such that $(α+t↓1)↑{(p↑d-1)/2}=
(α+t↓2)↑{(p↑d-1)/2}$, i.e., $\biglp(α+t↓1)/(a+t↓2)\bigrp↑{(p↑d-1)/2}=1$.
As $α$ runs through all the elements of degree $d$, so does the quantity
$(α+t↓1)/(α+t↓2)=1+(t↓1-t↓2)/(α+t↓2)$.

[We have $n(p,d)={1\over4}d↑{-1}\sum↓{c\rslash d}\biglp3+(-1)↑c\bigrp
\mu(c)(p↑{d/c}-1)$, which is about half the total number of irreducibles---exactly
half, in fact, when $d$ is odd.
This proves that $\gcd\biglp g↓d(x),(x+t)↑{(p↑d-1)/2}-1\bigrp$
has a good chance of finding factors of $g↓d(x)$ when $t$ is fixed and $g↓d(x)$ is
chosen at random; but a \α{probabilistic algorithm} is supposed to work with
guaranteed probability for fixed $g↓d(x)$ and random $t$, as in exercise↔29.]

\def\+{\hbox{$\Psi$\hskip-1.5pt}}
\ansno 32. (a)\9 Clearly $x↑n-1=\prod↓{d\rslash n}\+↓d(x)$, since every complex
$n$th root of unity is a primitive $d$th root for some unique $d\rslash n$.
The second identity follows from the first; and $\+↓n(x)$ has integer
coefficients since it is expressed in terms of products and quotients of monic
polynomials with integer coefficients.\xskip(b) The condition in the hint
suffices to prove that $f(x)=\+↓n(x)$, so we shall take the hint. When
$p$ does not divide $n$, we have $\gcd(x↑n-1,nx↑{n-1})=1$ modulo $p$, hence
$x↑n-1$ is squarefree modulo $p$. Given $f(x)$ and $\zeta$ as in the hint,
let $g(x)$ be the irreducible factor of $\+↓n(x)$ such that $g(\zeta↑p)=0$.
If $g(x)≠f(x)$ then both $f(x)$ and $g(x)$ are distinct factors of $\+↓n(x)$,
hence they are distinct factors of $x↑n-1$, hence they have no irreducible
factors in common modulo↔$p$. However, $\zeta↑p$ is a root of $f(x↑p)$,
so $\gcd\biglp g(x),f(x↑p)\bigrp≠1$ over the integers, hence $g(x)$ is
a divisor of $f(x↑p)$. By (5), $g(x)$ is a divisor of $f(x)↑p$, modulo $p$,
contradicting the assumption that $f(x)$ and $g(x)$ have no irreducible
factors in common. Therefore $f(x)=g(x)$.\xskip[The irreducibility of
$\+↓n(x)$ was first proved for prime $n$ by K. F. \α{Gauss} in {\sl Disquisitiones
Arithmetic\ae\ }(Leipzig, 1801), Art.\ 341, and for general $n$ by L.
\α{Kronecker,} {\sl J. de Math. Pures et Appliqu\'ees \bf19} (1854), 177--192.]

(c)\9 $\+↓1(x)=x-1$; and when $p$ is prime, $\+↓p(x)=1+x+\cdots+x↑{p-1}$.
If $n>1$ is odd, it is not difficult to prove that $\+↓{2n}(x)=\+↓n(-x)$.
If $p$ divides $n$, the second identity in (a) shows that $\+↓{pn}(x)=
\+↓n(x↑p)$. If $p$ does not divide $n$, we have $\+↓{pn}(x)=\+↓n(x↑p)/
\+↓n(x)$. For nonprime $n≤15$ we have $\+↓4(x)=x↑2+1$, $\+↓6(x)=
x↑2-x+1$, $\+↓8(x)=x↑4+1$, $\+↓9(x)=x↑6+x↑3+1$, $\+↓{10}(x)=
x↑4-x↑3+x↑2-x+1$, $\+↓{12}(x)=x↑4-x↑2+1$,
$\+↓{14}(x)=x↑6-x↑5+x↑4-x↑3+x↑2-x+1$, $\+↓{15}(x)=
x↑8-x↑7+x↑5-x↑4+x↑3-x+1$.\xskip[The formula $\+↓{pq}(x)=(1+x↑p+\cdots+x↑{(q-1)p})
(x-1)/(x↑q-1)$ can be used to show that $\+↓{pq}(x)$ has all coefficients
$\pm1$ or 0 when $p$ and $q$ are prime; but the coefficients of $\+↓{pqr}(x)$
can be arbitrarily large.]

\ansno 33. False; we lose all $p↓j$ with $e↓j$ divisible by
$p$. True if $p ≥ \\(u)$.\xskip[See exercise↔36.]

\ansno 34. [D. Y. Y. \α{Yun}, {\sl Proc.\ ACM Symp.\ Symbolic and Algebraic
Comp.\ }(1976), 26--35.]\xskip Set $\biglp t(x),v↓1(x),w↓1(x)\bigrp←\hbox{GCD}\biglp
u(x),u↑\prime(x)\bigrp$. If $t(x)=1$, set $e←1$; otherwise set $\biglp u↓i(x),
v↓{i+1}(x),w↓{i+1}(x)\bigrp←\hbox{GCD}\biglp v↓i(x),w↓i(x)-v↓{\!i}↑\prime(x)\bigrp$
for $i=1$, 2, $\ldotss$, $e-1$, until finding $w↓e(x)-v↓{\!e}↑\prime(x)=0$.
Finally set $u↓e(x)←v↓e(x)$.

To prove the validity of this algorithm, we observe that it computes the polynomials
$t(x)=u↓2(x)u↓3(x)↑2u↓4(x)↑3
\ldotsm$, $v↓i(x)=u↓i(x)u↓{i+1}(x)u↓{i+2}(x)\ldotsm$, and
$$\twoline{w↓i(x)=u↓{\!i}↑\prime(x)u↓{i+1}(x)u↓{i+2}(x)\ldotsm+
2u↓i(x)u↓{\!i+1}↑\prime(x)u↓{i+2}(x)\ldotsm}{3pt}{\null+
3u↓i(x)u↓{i+1}(x)u↓{\!i+2}↑\prime(x)\ldotsm+\cdotss.}$$
We have $\gcd\biglp t(x),w↓1(x)\bigrp=1$, since an irreducible factor of $u↓i(x)$
divides all but the $i$th term of $w↓1(x)$, and it is relatively prime to that
term. Fur\-ther\-more $\gcd\biglp u↓i(x),v↓{i+1}(x)\bigrp$ is clearly↔1.

[Exercise 2(b) indicates that comparatively few polynomials are squarefree, but
non-squarefree polynomials actually occur often in practice; hence this method
turns out to be quite important. See Paul S. \α{Wang} and Barry M. \α{Trager},
{\sl SIAM J. Computing \bf8} (1979), 300--305, for suggestions on how to
improve the efficiency when the given polynomial is already squarefree.]

\ansno 35. We have $w↓j(x)=\gcd\biglp u↓j(x),v↓{\!j}↑{\ast}(x)\bigrp\cdot
\gcd\biglp u↓{\!j+1}↑\ast(x),v↓j(x)\bigrp$, where$$u↓{\!j}↑\ast(x)=u↓j(x)
u↓{j+1}(x)\ldotsm\qquad\hbox{and}\qquad
v↓{\!j}↑\ast(x)=v↓j(x)v↓{j+1}(x)\ldotsm\,.$$
[\α{Yun} notes that the running time for squarefree factorization by the method
of exercise↔34 is at most about twice the running time to calculate $\gcd\biglp
u(x),u↑\prime(x)\bigrp$. Furthermore if we are given an arbitrary method for
discovering squarefree factorization, the method of this exercise leads to a
gcd procedure.\xskip(When $u(x)$ and $v(x)$ are squarefree, their gcd is
simply $w↓2(x)$ where $w(x)=u(x)v(x)=w↓1(x)w↓2(x)↑2$; the polynomials
$u↓j(x)$, $v↓j(x)$, $u↓{\!j}↑\ast(x)$, and $v↓{\!j}↑\ast(x)$ are all
squarefree.)\xskip Hence the problem of converting a primitive polynomial
of degree $n$ to its squarefree representation is computationally {\sl equivalent\/}
to the problem of calculating the gcd of two $n$th degree polynomials, in the
sense of asymptotic worst-case running time.]

\ansno 36. Let $U↓j(x)$ be the value computed for ``$u↓j(x)$'' by the procedure
of exercise↔34. If $\\(U↓1)+2\\(U↓2)+\cdots=\\(u)$, then $u↓j(x)=U↓j(x)$ for
all $j$. But in general we will have $e<p$ and $U↓j(x)=\prod↓{k≥0}u↓{j+pk}(x)$
for $1≤j<p$. To separate these factors further, we can calculate $t(x)/\biglp
U↓2(x)U↓3(x)↑2\ldotss U↓{p-1}(x)↑{p-2}\bigrp=\prod↓{j≥p}u↓j(x)↑{p\lfloor j/p\rfloor}
=z(x↑p)$. After \α{recursive}ly finding the squarefree representation of
$z(x)=\biglp z↓1(x),z↓2(x),\ldotss\bigrp$, we will have $z↓k(x)=\prod↓{0≤j<p}
u↓{j+pk}(x)$, so we can calculate the individual $u↓i(x)$ by the formula
$\gcd\biglp U↓j(x),z↓k(x)\bigrp=u↓{j+pk}(x)$ for $1≤j<p$. The polynomial
$u↓{pk}(x)$ will be left when the other factors of $z↓k(x)$ have been removed.

{\sl Note:} This procedure is fairly simple but the program is lengthy.
If one's goal is to have a short program for complete factorization modulo↔$p$,
rather than an extremely efficient one, it is probably easiest to
modify the \α{distinct-degree factorization} routine so that it casts out
$\gcd\biglp x↑{p↑d}-x,u(x)\bigrp$ several times for the same value of $d$
until the gcd is↔1. In this case you needn't begin by calculating $\gcd\biglp
u(x),u↑\prime(x)\bigrp$ and removing multiple factors as suggested in the text,
since the polynomial $x↑{p↑d}-x$ is squarefree.

\ansno 37. The exact probability is $\prod↓{j≥1}(a↓{jp}/p↑j)↑{k↓j}/k↓j!$,
where $k↓j$ is the number of $d↓i$ that are
equal to $j$. Since $a↓{jp}/p↑j\approx 1/j$
by exercise↔4, we get the formula of exercise 1.3.3--21.

{\sl Notes:} This exercise says that if we fix the prime $p$ and let the
polynomial $u(x)$ be random, it will have certain probability of splitting
in a given way modulo $p$. A much harder problem is to fix the polynomial $u(x)$
and to let $p$ be ``random''; it turns out that the same asymptotic result holds
for almost all $u(x)$.\xskip G. \β{Frobenius} proved in 1880 that the integer
polynomial $u(x)$ splits modulo $p$ into factors of degrees $d↓1$, $\ldotss$, $d↓r$,
when $p$ is a large prime chosen at random, with probability equal to the
number of permutations in the \β{Galois group} $G$ of $u(x)$ having cycle lengths
$\{d↓1,\ldotss,d↓r\}$ divided by the total number of permutations in $G$.\xskip
$\biglp$If $u(x)$ has rational coefficients and distinct roots $\xi↓1$,
$\ldotss$,↔$\xi↓n$ over the complex numbers, its Galois group is the (unique) group $G$
of permutations such that the polynomial $\prod↓{p(1)\ldotsm p(n)\in G}
\biglp z+\xi↓{p(1)}y↓1+\cdots+\xi↓{p(n)}y↓n\bigrp=U(z,y↓1,\ldotss,y↓n)$ has rational
coefficients and is irreducible over the rationals.$\bigrp$\xskip Furthermore
B.↔L. \α{van↔der↔Waerden} proved in 1934 that almost all polynomials of degree $n$
have the set of all $n!$ permutations as their Galois group. Therefore
almost all fixed irreducible polynomials $u(x)$ will factor as we might expect them
to, with respect to randomly chosen large primes $p$.\xskip References:
{\sl Sitzungsberichte K\"onigl.\ Preu\ss.\ Akad.\ Wiss.\ }(Berlin: 1896),
\hbox{689--703}; {\sl Math.\ Annalen \bf109} (1934), 13--16. See also
N. \α{Chebotarev}, {\sl Math.\ Annalen \bf95} (1926), for a generalization of
Frobenius's theorem to conjugacy classes of the Galois group.

\ansno 38. (Partial solution by Peter \α{Weinberger}.)\xskip
The average number of 1-cycles in a randomly chosen element of any transitive
\α{permutation} group $G$ on $n$ objects is↔1, since the probability is $1/n$
that any given object is fixed. Since Galois groups are always transitive, the
remarks in the previous answer show that a fixed irreducible polynomial has
exactly one linear factor modulo↔$p$, on the average, as $p→∞$. Thus,
{\sl the average number of linear factors of $u(x)$ modulo↔$p$ is the
number of irreducible factors of $u(x)$ over the integers.}

Weinberger [{\sl Proc.\ Symp.\ Pure Math.\ \bf24} (Amer.\ Math.\ Soc., 1973),
321--332] has proved that if the \α{generalized Riemann hypothesis} (\α{GRH})
holds---this is a conjecture about the zeros of a generalized \α{zeta
function}---then there is an absolute constant $A↓1$ with the following property:
The number of prime ideals of norm $≤x$, in any \α{algebraic number field} of
degree↔$n$, differs from $\int↓2↑x dt/\!\ln t$ by at most $A↓1nx↑{1/2}\ln(x\Delta)$,
where $\Delta$ is the absolute value of the \α{discriminant} of the irreducible
polynomial $u$ that defines the field. The number of prime ideals of norm $≤x$
is at most $nx↑{1/2}$ different from the total number of linear factors of $u$
modulo primes $≤x$, since such linear factors correspond to ideals of norm↔$p$,
while other prime ideals have norms $≥p↑2$. Consequently if we let $N(x)$ be the
total number of linear factors of a given primitive polynomial $u$, modulo all
primes $≤x$, then the GRH implies that there is an absolute constant $A↓2$
such that $|N(x)/π(x)-r|<A↓2nx↑{-1/2}(\ln x)(\ln x\Delta)$. A proof of GRH
would yield a ``short'' proof of the number of irreducible factors of any primitive
polynomial $u$ over the integers, since we could evaluate $N(x)$ for a value of
$x$ sufficiently large to make this error bound less than ${1\over2}$. Unfortunately
$A↓2$ is quite large.
%folio 819 galley 4b (C) Addison-Wesley 1978	*

\ansbegin{4.6.3}

\ansno 1. $x↑m$, where $m=2↑{λ(n)}$, the highest
power of 2 less than or equal to $n$.

\ansno 2. Assume that $x$ is input in register↔A\null,
and $n$ in location↔\.{NN}; the output is in register↔X.

{\yyskip\tabskip30pt \mixfive{\!
01⊗A1⊗ENTX⊗1⊗1⊗\understep{A1. Initialize.}\cr
02⊗⊗STX⊗Y⊗1⊗$Y←1$.\cr
03⊗⊗STA⊗Z⊗1⊗$Z←x$.\cr
\\04⊗⊗LDA⊗NN⊗1⊗$N←n$.\cr
05⊗⊗JMP⊗2F⊗1⊗To A2.\cr
\\06⊗5H⊗SRB⊗1⊗L+1-K\cr
07⊗⊗STA⊗N⊗L+1-K⊗$N←\lfloor N↓{\null}/2\rfloor$.\cr
\\08⊗A5⊗LDA⊗Z⊗L⊗\understep{A5. S\hskip2.5pt}{\sl\hskip-2.5pt
q}\understep{uare $Z$.}\cr
09⊗⊗MUL⊗Z⊗L⊗$Z\times Z\mod w$\cr
10⊗⊗STX⊗Z⊗L⊗\qquad$→Z$.\cr
\\11⊗A2⊗LDA⊗N⊗L⊗\understep{A2. Halve $N$.}\cr
12⊗2H⊗JAE⊗5B⊗L+1⊗To A5 if $N$ is even.\cr
13⊗⊗SRB⊗1⊗K\cr
14⊗A4⊗JAZ⊗4F⊗K⊗Jump if $N=1$.\cr
15⊗⊗STA⊗N⊗K-1⊗$N←\lfloor N↓{\null}/2\rfloor$.\cr
\\16⊗A3⊗LDA⊗Z⊗K-1⊗\understep{A3. Multi}{\sl p\hskip-3pt}\understep{\hskip
3pt l\hskip1pt}{\sl\hskip-1pt y\hskip-2pt}\understep{\hskip2pt\ $Y$ b\hskip1pt
}{\sl\hskip-1pt y\hskip-2pt}\understep{\hskip2pt\ $Z$.}\cr
17⊗⊗MUL⊗Y⊗K-1⊗$Z\times Y\mod w$\cr
18⊗⊗STX⊗Y⊗K-1⊗\qquad$→Y$.\cr
19⊗⊗JMP⊗A5⊗K-1⊗To A5.\cr
\\20⊗4H⊗LDA⊗Z⊗1\cr
21⊗⊗MUL⊗Y⊗1⊗Do the final multiplication.\quad\blackslug\cr}}

\yyskip\noindent [It would be better programming
practice to change the instruction in line 05 to ``\.{JAP}'', followed
by an error indication. The running time is $21L + 16K + 8$,
where $L = λ(n)$ is one less than the number of bits in the
binary representation of $n$, and $K = \nu (n)$ is the number
of 1 bits in that representation.]

For the serial program, we may assume that $n$
is small enough to fit in an index register; otherwise serial
exponentiation is out of the question. The following program
leaves the output in register↔A:

{\yyskip\tabskip30pt\mixfive{\!
01⊗S1⊗LD1⊗NN⊗1⊗$\rI1←n$.\cr
02⊗⊗STA⊗X⊗1⊗$X←x$.\cr
03⊗⊗JMP⊗2F⊗1\cr
\\04⊗1H⊗MUL⊗X⊗N-1⊗$\rA\times X\mod w$\cr
05⊗⊗SLAX⊗5⊗N-1⊗\qquad$→\rA$.\cr
\\06⊗2H⊗DEC1⊗1⊗N⊗$\rI1←\rI1-1$.\cr
07⊗⊗J1P⊗1B⊗N⊗Multiply again if $\rI1>0$.\quad\blackslug\cr}}

\yyskip\noindent The running time for this program is $14N-7$; it is faster than
the previous program when $n≤7$, slower when $n≥8$.


\ansno 3. The sequences of exponents are:\xskip (a) 1, 2, 3,
6, 7, 14, 15, 30, 60, 120, 121, 242, 243, 486, 487, 974, 975
[16 multiplications];\xskip (b) 1, 2, 3, 4, 8, 12, 24, 36, 72, 108,
216, 324, 325, 650, 975 [14 multiplications];\xskip (c) 1, 2, 3, 6,
12, 15, 30, 60, 120, 240, 243, 486, 972, 975 [13 multiplications];\xskip
(d) 1, 2, 3, 6, 12, 15, 30, 60, 75, 150, 300, 600, 900, 975
[13 multiplications].\xskip [The smallest possible number of multiplications
is 12; this is obtainable by combining the factor method with
the binary method, since $975 =15 \cdot (2↑6 + 1)$.]

\ansno 4. $(777777)↓8 = 2↑{18} - 1$.

\def\ansalgstep #1 #2. {\anskip\noindent\hbox to 40pt{\!
\hbox to 19pt{\hss\bf#1\ }\hfil\bf#2. }\hangindent 40pt}
\ansalgstep 5. T1. [Initialize.]\xskip Set $\.{LINKU}[j]
← 0$ for $1 ≤ j ≤ 2↑r$, and set $k ← 0$, $\.{LINKR}[0] ← 1$, $\.{LINKR}[1]
← 0$.

\ansalgstep{} T2. [Change level.]\xskip(Now level $k$
of the tree has been linked together from left to right, starting
at $\.{LINKR}[0]$.) If $k = r$, the algorithm terminates. Otherwise
set $n ← \.{LINKR}[0]$, $m ← 0$.

\ansalgstep{} T3. [Prepare for $n$.]\xskip(Now $n$
is a node on level $k$, and $m$ points to the rightmost node
currently on level $k + 1$.)\xskip Set $q ← 0$, $s ← n$.

\ansalgstep{} T4. [Already in tree?]\xskip(Now $s$ is
a node in the path from the root to $n$.)\xskip If $\.{LINKU}[n + s]
≠ 0$, go to T6 (the value $n + s$ is already in the tree).

\ansalgstep{} T5. [Insert below $n$.]\xskip If $q
= 0$, set $m↑\prime ← n + s$. Then set $\.{LINKR}[n + s] ← q$, $\.{LINKU}[n
+ s] ← n$, $q ← n + s$.

\ansalgstep{} T6. [Move up.]\xskip Set $s ←\.{LINKU}[s]$.
If $s ≠ 0$, return to T4.

\ansalgstep{} T7. [Attach group.]\xskip If $q ≠ 0$, set
$\.{LINKR}[m] ← q$, $m ← m↑\prime $.

\ansalgstep{} T8. [Move $n$.]\xskip Set $n ←\.{LINKR}[n]$.
If $n ≠ 0$, return to T3.

\ansalgstep{} T9. [End of level.]\xskip Set $\.{LINKR}[m]
← 0$, $k ← k + 1$, and return to T2.\quad\blackslug

\ansno 6. Prove by induction that
the path to the number $2↑{e↓0} + 2↑{e↓1} + \cdots
+ 2↑{e↓t}$, if $e↓0 > e↓1 > \cdots >e↓t ≥ 0$, is 1, 2,
$2↑2$, $\ldotss$, $2↑{e↓0}$, $2↑{e↓0} + 2↑{e↓1}$, $\ldotss$,
$2↑{e↓0}+2↑{e↓1}+ \cdots + 2↑{e↓t}$; furthermore,
the sequences of exponents on each level are in decreasing lexicographic
order.

\ansno 7. The binary and factor methods require
one more step to compute $x↑{2n}$ than $x↑n$; the power tree
method requires at most one more step. Hence (a) $15 \cdot 2↑k$;
(b) $33 \cdot 2↑k$; (c)↔$23 \cdot 2↑k$; $k = 0$, 1, 2, 3,
$\ldotss\,$.

\ansno 8. The power tree always includes the node
$2m$ at one level below $m$, unless it occurs at the same level
or an earlier level; and it always includes the node $2m + 1$
at one level below $2m$, unless it occurs at the same level or an earlier level.\xskip
[It is not true that $2m$ is a son of $m$ in the power tree for all↔$m$; the
smallest example where this fails is $m=2138$, which appears on level↔15, while
4276 appears elsewhere on level↔16. In fact, $2m$ sometimes occurs on the same level
as $m$; the smallest example is $m=6029$.]

\ansno 9. Start with $N←n$, $Z←x$, and $Y↓k←1$ for $1≤k<m$; in general we will have
$x↑n=Y↓1Y↓{\!2}↑2\ldotsm Y↓{\!m-1}↑{m-1}Z↑N$. If $N>0$, set $k←N\mod m$, and if
$k≠0$ set $Y↓k←Y↓k\cdot Z$. Then set $Z←Z↑m$, $N←\lfloor N\!/m\rfloor$, and repeat. Finally
set $Y↓k←Y↓k\cdot Y↓{k+1}$ for $k=m-2$, $m-3$, $\ldotss$,↔1; the answer is
$Y↓1\ldotsm Y↓{m-1}$.

\ansno 10. By using the ``\.{FATHER}'' representation discussed
in Section 2.3.3: Make use of a table $f[j]$, $1 ≤ j ≤ 100$,
such that $f[1] = 0$ and $f[j]$ is the number of the node
just above $j$ for $j ≥ 2$.\xskip (The fact that each node of this
tree has degree at most two has no effect on the efficiency
of this representation; it just makes the tree look prettier
as an illustration.)

\ansno 11. 1, 2, 3, 5, 10, 20, (23 or 40), 43; 1, 2, 4, 8, 9,
17, (26 or 34), 43; 1, 2, 4, 8, 9, 17, 34, (43 or 68), 77; 1,
2, 4, 5, 9, 18, 36, (41 or 72), 77. If either of the latter
two paths were in the tree we would have no possibility for
$n = 43$, since the tree must contain either 1, 2, 3, 5 or 1,
2, 4, 8, 9.

\ansno 12. No such infinite tree can exist, since $l(n) ≠ l↑\ast(n)$
for some $n$.